[백준] 2178번. 미로 탐색(JAVA)

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

---

문제

---

풀이

import java.io.*;
import java.util.*;
public class Main {
    static int[][] arr;
    static int[] dx = {0, 1, 0, -1};
    static int[] dy = {1, 0, -1, 0};
    static boolean[][] visited;
    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];
        visited = new boolean[n][m];
        for(int i = 0; i < n; i++){
            st = new StringTokenizer(br.readLine());
            String row = st.nextToken();
            for(int j = 0; j < m; j++){
                arr[i][j] = Integer.parseInt(row.substring(j, j+1));
            }
        }

        Bfs(0,0);

        System.out.println(arr[n-1][m-1]);

    }

    public static void Bfs(int i, int j){
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[] {i, j});
        while(!queue.isEmpty()){
            int now[] = queue.poll();
            visited[i][j] = true;
            for(int k = 0; k < 4; k++){
                int x = now[0] + dx[k];
                int y = now[1] + dy[k];
                if(x >= 0 && y >= 0 && x < n && y < m){
                    if(arr[x][y] != 0 && !visited[x][y]){
                        visited[x][y] = true;
                        arr[x][y] = arr[now[0]][now[1]] + 1;
                        queue.offer(new int[] {x , y});
                    }
                }
            }
        }
    }
}

 

입력을 받을 때 주의할 점은, StringTokenizer을 사용하여 nextToken()으로 받을 경우 띄어쓰기를 기준으로 구분되기 때문에 한 줄 전체로 들어오는 것을 받을 수 없다. 따라서 문자열을 받은 뒤에 이를 다시 substring으로 분해해서 저장해주어야 한다.

 

깊이 위주로 탐색하는 dfs 방식을 사용하면 다시 올라오는 경우에 -1을 해줘야 할 수 있기 때문에 bfs방식이 유리하다고 판단했다.

 

먼저

int x = now[0] + dx[k];
int y = now[1] + dy[k];
if(x >= 0 && y >= 0 && x < n && y < m){

를 이용하여 현재 이동하려고 하는 좌표가 유효한지 먼저 판단한다. (NullPointerException을 방지하는 절차이다.)

 

좌표가 유효한 경우 0이 아닌지만 검사한다. 다른 bfs와 다르게 0이 아닌지만 검사하는 이유는 이동하는 즉시 방문값을 측정하려고 하기 때문이다. 또한, 방문했던 좌표인지도 검사한다.

 

방문했던 좌표가 아니라면 방문한 좌표로 표시한 뒤, 이전 값의 +1을 해줌으로써 값을 갱신한다.