[ 백준 ] 2178번 - 미로 탐색

< 문제 정보 >

[ 문제 ]

  0은 이동 불가능한 칸, 1은 이동 가능한 칸을 의미하는 N x M 크기의 미로가 주어졌을 때, 첫 번째 칸에서 시작하여, 가장 끝 칸으로 이동하기 위한 최소의 이동 수를 구하는 문제

[ 예시 ]

• 입력

4 6
101111
101010
101011
111011

※ 4 : N개의 줄, 5 : M개의 줄

• 출력

15

[ 규칙 ]

• 두 정수 N, M(2 ≤ N, M ≤ 100)

[ 백준 ]

• BFS
• 링크

< 풀이 >

•   미로는 붙어있는 칸 즉, 상하좌우로만 이동 가능하다. 상하좌우는 현재 좌표에서 (1,0) / (-1,0) / (0,-1) / (0,1)로 움직이기 때문에 이를 나타내는 배열 2개를 사전에 선언하여 이용한다. 현재 좌표 값 x와 y에 앞서 선언한 두 배열을 더하면, 다음 이동 칸을 의미하게 된다.
•   여기서 다음 이동 칸은 미로를 벗어나선 안 되기에 0보다 작아서도, M과 N보다 커서도 안 된다.
•   다음 이동 칸에 1을 더하여, 이동한 값을 구한다.
  
  [ 입력 행렬 ]

  	0	1	2	3	4	5
  0	1	0	1	1	1	1
  1	1	0	1	0	1	0
  2	1	0	1	0	1	1
  3	1	1	1	0	1	1

  
  [ 최종 결과 행렬 ]

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

  → 15 출력

< 코드 >

public class BaekJoon2178 {
    static int dx[] = { 1, 0, -1, 0 };
    static int dy[] = { 0, 1, 0, -1 };
    static int N, M;
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(bf.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        boolean[][] visited = new boolean[N][M];
        int[][] graph = new int[N][M];
        for(int i=0;i<N;i++) {
            String s = bf.readLine();
            graph[i] = Stream.of(s.split("")).mapToInt(Integer::parseInt).toArray();
        }
        BaekJoon2178 baekJoon2178 = new BaekJoon2178();
        baekJoon2178.bfs(graph, 0, 0, visited);
    }
    private void bfs(int[][] graph, int x, int y, boolean[][] visited) {
        Queue<int[]> queue = new LinkedList<>();
        queue.add(new int[] {x, y});
        visited[x][y] = true;
        while(!queue.isEmpty()) {
            int[] v = queue.poll();
            int nowX = v[0];
            int nowY = v[1];
            for (int i=0;i<dx.length;i++) {
                int nextX = nowX + dx[i];
                int nextY = nowY + dy[i];
                if (nextX < 0 || nextY<0 || nextX>=N || nextY>=M || visited[nextX][nextY] || graph[nextX][nextY] == 0)
                    continue;
                queue.add(new int[] {nextX,nextY}); // 이동 좌표값 추가
                visited[nextX][nextY] = true;   // 방문처리
                graph[nextX][nextY] = graph[nowX][nowY] + 1;    // 거리 측정. 누적해서 측정한 거리 + 1
            }
        }
        System.out.println(graph[N-1][M-1]);
    }
}

---

듣기론 DFS를 이용하면 시간 초과가 걸린다고 한다. DFS로도 풀어봐야겠다. DFS와 BFS를 이용한 좌표 이동 문제는 코딩테스트에서도 출제된 걸 풀어봤기 때문에, 잘 알아두면 좋을 듯하다.