백준 2178. 미로 탐색(JAVA)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {

    static int[][] arr;
    static boolean[][] visit;
    static int cnt = 0;
    static int N, M;

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        
        st = new StringTokenizer(br.readLine());
         N = Integer.parseInt(st.nextToken());
         M = Integer.parseInt(st.nextToken());

        arr = new int[N][M];
        visit = new boolean[N][M];

        for (int i = 0; i < N; i++) {
            
            String str = br.readLine();
            
            for (int j = 0; j < M; j++) {
                
                arr[i][j] = str.charAt(j) - '0';
                
            }
        }
        bfs();
        System.out.println(arr[N-1][M-1]);

    }

    static void bfs() {
        
        int[] dr = {-1, 1, 0, 0};
        int[] dc = {0, 0, 1, -1};
        
        Queue<Integer> q1 = new LinkedList<>();
        Queue<Integer> q2 = new LinkedList<>();

        q1.offer(0);
        q2.offer(0);

        visit[0][0] = true;
        
        while(!q1.isEmpty()) {
            
            int i = q1.poll();
            int j = q2.poll();

            for (int a = 0; a < 4; a++) {
                
                int nr = i + dr[a];
                int nc = j + dc[a];

                if (nr >= 0 && nc >= 0 && nr < N && nc < M) {
                    
                    if (arr[nr][nc] == 1 && !visit[nr][nc]) {
                        
                        q1.offer(nr);
                        q2.offer(nc);

                        visit[nr][nc] = true;

                        arr[nr][nc] = arr[i][j] + 1;

                    }
                }
            }
        }
    }
}

○ 문제 요약

N X M 크기의 미로에서 (1,1)을 시작점으로 하여 (N, M)까지 이동해야 한다고 할 때, 지나가야 하는 최소의 칸을 구해라. 

 

○ 문제 풀이

이번에는 BFS를 사용했고 입력은 예제에 나와있는 것을 사용해서 문제 풀이를 설명하고자 한다.

예제 입력 1

먼저 현재 좌표 기준으로 상, 하, 좌, 우 좌표들의 값을 알아내기 위해 dr배열과 dc배열을 만들었다. 

Queue를 두 개 만들어서 시작점 좌표를 넣어주고 visit 배열의 (0,0) 좌표도 true를 넣어준다.

Queue에 넣은 값을 하나씩 빼서 i와 j에 넣어주고 아래 그림과 같이 연산을 해서 현재 좌표 기준 상, 하, 좌, 우 좌표들의 좌표 값을 구한다.

첫 번째 if문에서 위에서 구한 nr과 nc의 값이 조건에 맞는지 확인하고 조건에 부합하면 두 번째 if문으로 들어간다.

두 번째 if문의 조건에 부합하면 현재 좌표 값에 1을 더한 값을 다음 좌표 값에 넣어준다. 이 과정을 도착점까지 하면 아래와 같은 2차원 배열이 만들어진다. 

bfs() 메서드를 실행하고 나면 위와 같은 결과가 나오는데, 마지막 좌표 값을 출력해줌으로써 최소 몇 개의 칸을 지나야 하는지 알 수 있다. 

 

○ 결과