[브루트 포스 / BOJ 14497 / C++] 주난의 난(難)

https://www.acmicpc.net/problem/14497

14497번: 주난의 난(難)

1) 상하좌우로 dfs를 시행한다. (총 4번의 dfs)
(참고로 x,y,x2,y2 input 모두 (1,1) ,,, (M,N)으로 들어오므로 -1 해줘야한다..)
2) 1번의 점프가 끝났으므로, res를 업데이트
3) 만약 dfs에서 #를 찾았다면(chk==1) res를 출력하고 종료.
4) 아직 #을 못찾았다면, 다시 dfs를 수행해야하므로 사용된 vis를 0으로 업데이트 해준다.

이 문제는 간단한 구현문제다!

 

상하좌우로 dfs나 bfs를 시행하여 마주치는 모든 1를 0으로 바꾼다.

 

우선 solve 함수를 보자!

 

1) 상하좌우로 dfs를 시행한다. (총 4번의 dfs)

(참고로 x,y,x2,y2 input 모두 (1,1) ,,, (M,N)으로 들어오므로 -1 해줘야한다..)

2) 1번의 점프가 끝났으므로, res를 업데이트

3) 만약 dfs에서 #를 찾았다면(chk==1) res를 출력하고 종료.

4) 아직 #을 못찾았다면, 다시 dfs를 수행해야하므로 사용된 vis를 0으로 업데이트 해준다.

 

이제 dfs는 우리가 알던 그 dfs로 시전해준다.

 

다만, 조건을 추가한다. 바로 dfs가 #을 찾으면(x2-1,y2-1) 찾았다고 표시를 해준다.

또한, 만나는 '1' 마다 '0'으로 바꿔준다!

 

그리고 보통은 반복문 안에 dfs() 함수를 돌릴때는 vis를 초기화시키고 dfs를 돌리는데, 이거는 그럴 필요 없다.

왜냐하면 어차피 상하좌우 모두 탐색할 예정이니, 괜히 vis를 초기화시키면 갔던 장소를 또가게 되고, 한번의 점프 시도로 모든 1들이 0으로 바뀌어 무한 루프에 빠질수도 있다.

 

이런 부분을 주의해서 구현해주면 풀린다!

 

 

 

#include <bits/stdc++.h>

using namespace std;

int N, M, x, y, x2, y2, res, chk;
char bd[304][304];
int vis[304][304];

int dy[4] = {0, 1, 0, -1};
int dx[4] = {1, 0, -1, 0};

void dfs(int n1, int n2){
    if(n1 >= N || n2 >= M || n1 < 0 || n2 < 0 ) return; // n1, n2가 조건에 안맞으면 종료.
    if(vis[n1][n2]) return;
    if(n1==(x2-1) && n2==(y2-1)) {chk=1; return;}
    
    if(bd[n1][n2]=='1'){ // 만약 현위치가 (n1,n2) 면은 함수를 종료하고
        bd[n1][n2] = '0';
        vis[n1][n2]=1; // 현위치 방문표시
        return;
    }
    
    vis[n1][n2] = 1; // 방문표시
    
    for(int i = 0; i < 4 ; i++){
        int ny = n1 + dy[i];
        int nx = n2 + dx[i];
        
        dfs(ny,nx);
        
    }
    
    
    
    return;
}

void solve(){
    while(true){
        for(int i = 0 ; i < 4 ; i++){
            dfs(x-1 + dy[i], y-1 + dx[i]);
        } // dfs 상하좌우 1번씩.
        
        res++; // 1번 점프 끝남.
        if(chk) {cout << res; return;}
        
        memset(vis, 0, sizeof(vis)); // vis 초기화
    }
    
    return;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    cin >> N >> M >> x >> y >> x2 >> y2;
    
    for(int i = 0 ; i < N ; i++){
        string s;
        cin >> s;
        for(int j = 0 ; j < M ; j++){
            bd[i][j] = s[j];
        }
    }
    
    solve();
    
}