[백준]JAVA - 2178번: 미로탐색

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

2178번: 미로 탐색

해당 문제는 (0, 0)에서 출발해서 (N, M)까지 최단 경로를 구하는 bfs 문제이다. 

서로 인접한 칸만 이동할 수 있으며 1은 이동할 수 있는 칸, 0은 벽을 의미한다.

예제 1번을 보면서 문제를 이해해보겠다.

예제 1번의 최단 경로를 그려보면 위와 같다. 이러한 유형의 문제는 대부분 입력 값을 넣어줄 Map 배열과 방문 여부를 판단하는 visited 배열 두 가지가 필요하다. 

int[][] map = new int[N+1][M+1];
int[][] ans = new int[N+1][M+1];

필자는 방문 여부를 판단하는 visited 배열 대신 '1'인 값은 전부 방문을 하지 않았다고 가정하고 최단 거리를 입력하는 ans 배열을 만들었다.

 

이제 (0, 0)에서 출발해서 '1'을 찾으면서 (N,M)까지의 거리를 계산해주면 된다. 

출발점의 좌표 값 (0, 0)을 Queue에 입력 후, 상하좌우에 '1'인 값을 찾아서 이전 좌표값에 +1을 해주면서 나아가면 된다.

ans[1][1] = 1;
Queue<Node> q = new LinkedList<>();		
q.add(new Node(1, 1));
		
while(!q.isEmpty()) {
    Node now = q.poll();
			
    for (int i=0; i<4; i++) {
        int row = now.x + x[i];
        int col = now.y + y[i];
				
        if (row > 0 && row < N+1 && col > 0 && col < M+1 && map[row][col] == 1 && ans[row][col] == 0) {
            q.add(new Node(row, col));
            ans[row][col] = ans[now.x][now.y] + 1;
        }
				
        // 도착지에 도달한 경우 반복문 탈출
        if (row == N && col == M) {
            System.out.println(ans[row][col]);
            return;
        }
    }
}

위의 코드를 끝까지 돌리면 ans배열이 아래와 같이 변경된다.

코드에서 '1'이 아닌 값은 이미 방문이 완료되었다고 판단하고 재방문을 하지 않기 때문에 (N, M)까지의 최단 경로를 찾을 수 있는 것이다. 

 

<최종코드>

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
		
        int[] x = {-1, 0, 1, 0};
        int[] y = {0, -1, 0, 1};
		
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        int[][] map = new int[N+1][M+1];
        int[][] ans = new int[N+1][M+1];
		
        class Node {
            int x;
            int y;
			
            public Node (int x, int y) {
                this.x = x;
                this.y = y;
            }
        }
		
        for (int i=1; i<N+1; i++) {
            String str = br.readLine();
            for (int j=1; j<M+1; j++) {
                map[i][j] = str.charAt(j-1) - '0';
            }
        }
		
        ans[1][1] = 1;
        Queue<Node> q = new LinkedList<>();		
        q.add(new Node(1, 1));
		
        while(!q.isEmpty()) {
            Node now = q.poll();
			
            for (int i=0; i<4; i++) {
                int row = now.x + x[i];
                int col = now.y + y[i];
				
                if (row > 0 && row < N+1 && col > 0 && col < M+1 && map[row][col] == 1 && ans[row][col] == 0) {
                    q.add(new Node(row, col));
                    ans[row][col] = ans[now.x][now.y] + 1;
                }
				
                // 도착지에 도달한 경우 반복문 탈출
                if (row == N && col == M) {
                    System.out.println(ans[row][col]);
                    return;
                }
            }
        }
    }
}