2178번

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

2178번: 미로 탐색

이번 문제는 DFS로 풀려고 노력해봤지만 못풀었다..

원인은 문제의 예제 마지막에 주어진 원순회가 있는 예제 때문이다. 백트래킹 방식으로 구현을 하였는데 이 과정에서 원순회를 만나면 무한 순회를 돌아서 stackoverflow가 떠버린다.. 혹시 DFS로 풀 해결책을 알고 있는 분이 있다면 한 수 가르쳐 주시면 좋겠다..

 

그래서 방법을 바꾸어 BFS로 해결책을 돌렸다.

BFS는 여느때와 다름없이 큰틀은 똑같이 잡고 여기서 갯수를 세는 과정만 고려하면 되는데, 여기서 주의할 것은 클래스 필드로 갯수를 셀 변수를 두면 값을 구하기 힘들것이다. 왜냐하면 경로와 관련없는 값을 꺼낼때도 갯수값이 올라가서 불필요한 증가가 생기기때문이다.

따라서 내부에 두어야한다.

내부에 둔다는 것은 시작지점을 1로 둔다면 처음 인접한 지역들에는 2를 두고 2인 지역들과 인접한 지역은 3을 두는 식으로 점차 도착지점에 도달하면서 갯수를 구할 수 있다.

1		1	1	1	1
1		1		1
1		1		1	1
1	1	1		1	1

 위와 같은 미로가 있다고 했을 때, 시작지점을 기준으로 갯수를 세는 것이다.

1		9	10	11	12
2		8		12
3		7		13	14
4	5	6		14	15

또 다른 예시 미로를 보면, 아래와 같다.

1	1		1	1
1	1		1	1
1	1	1	1	1	1
1	1	1	1		1

1	2		8	9
2	3		7	8	9
3	4	5	6	7	8
4	5	6	7		9

위의 미로를 보면 확실히 어떤 느낌인지 알 수 있을 것이다.

내부에서 즉, 인접한 값들을 같은 값으로 증가시키면서 값을 구하는 것이다.

 

정답코드는 아래와 같다.

package backjoon.b2178;
import java.io.*;
import java.util.*;
public class b2178 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        int[][] table = new int[N][M];
        for(int i=0; i<N; i++){
           String s = br.readLine();
            for(int j=0; j<M; j++){
                table[i][j]= Integer.parseInt(String.valueOf(s.charAt(j)));
            }
        }
        Graph g = new Graph(N,M,table);
        /*g.dfs(0,0,1);
        int min = Integer.MAX_VALUE;
        for (Integer integer : g.num) {
            if(integer<min){
                min=integer;
            }
        System.out.println(min);
        }*/
        g.bfs(0,0);
        System.out.println(g.count);
    }
}
class Graph{
    int[][] table;
    int N;
    int M;
    int count=0;
    ArrayList<Integer> num = new ArrayList<>();
    int[] dx = {-1, 0, 1, 0};
    int[] dy = {0, -1, 0, 1};
    Queue<target> queue = new LinkedList<>();
    public Graph(int N, int M, int[][] table){
        this.table=table;
        this.N=N;
        this.M=M;
    }
    public void dfs(int Rx, int Ry, int count){
        if(Rx==N-1&&Ry==M-1){
            num.add(count);
            return;
        }
        table[Rx][Ry]=0;
        for(int i=0; i<4; i++){
            int x = Rx+dx[i];
            int y = Ry+dy[i];
            if(x>=0 && y>=0 && x<N && y<M && table[x][y]==1){
                dfs(x,y,count+1);
                //table[Rx][Ry]=1;
            }
        }
    }
    public void bfs(int Rx, int Ry){
        table[Rx][Ry]=0;
        int cnt=1;
        queue.add(new target(Rx,Ry,cnt));
        while (!queue.isEmpty()){
            target tmp = queue.poll();
            if(tmp.x==N-1&&tmp.y==M-1){
                count=tmp.cnt;
            }
            for(int i=0; i<4; i++){
                int x = tmp.x+dx[i];
                int y = tmp.y+dy[i];
                if(x>=0&&y>=0&&x<N&&y<M&&table[x][y]==1){
                    table[x][y]=0;
                    queue.add(new target(x,y,tmp.cnt+1));
                }
            }
        }
    }
}
class target{
    int x;
    int y;
    int cnt;
    public target(int x, int y, int cnt) {
        this.x = x;
        this.y = y;
        this.cnt = cnt;
    }
}