백준 2178: 미로 탐색 (java)

알고리즘

BFS: 큐

 

체감 난이도

★ ★ ★ ★ ★

 

다시 풀 수 있는가?

NO

 

---

 

1. 공백 없는 문자 받기

 

charAt(int i) - '0'을 통해 char형의 문자들을 int형으로 변환시킬 수 있다.

 

        for (int i = 0; i < N; i++) {
            String s = br.readLine();
            for (int j = 0; j < M; j++) {
                arr[i][j] = s.charAt(j) - '0'; // 공백 없는 문자 split 해서 받기
            }
        }

 

2. 큐에 배열 설정

 

큐에 배열도 저장할 수 있다.

선언할 때는 Queue<int[]>로 하면 되고,

초기화할 때는 add(new int[] {0, 0}) 이런 형식으로 하면 된다.

 

        Queue<int[]> q = new LinkedList<>();
        q.add(new int[] {0, 0}); // 이렇게 초기화 !

 

그러면 이런 형식으로 사용할 수 있지롱

 

            int[] curr = q.poll();
            int currX = curr[0];
            int currY = curr[1];

 

3. 반복문 조건 확인

 

반복문 조건이 4까지인 이유는, 상하좌우 4개의 방향에 대해 반복적으로 탐색하기 위해서이다.

 

            for (int i = 0; i < 4; i++) {
            ...
            }
        }

 

4. 다음 좌표

 

q.poll() 해서 현재위치를 먼저 뽑아온 후,

 

다음에 탐색할 좌표를 설정한다.

 

                int nextX = currX + dx[i];
                int nextY = currY + dy[i];

 

5. 좌표 예외처리 & 저장

 

다음 좌표가 배열을 벗어나면 다음 반복문으로 넘기기

 

                if (nextX < 0 || nextY < 0 || nextX >= N || nextY >= M) {
                    continue;
                }

 

다음 좌표가 이미 방문되었거나, 0이라 막혀있다면 다음 반복문으로 넘기기

 

                if (isVisited[nextX][nextY] || arr[nextX][nextY] == 0) {
                    continue;
                }

 

만약 위 예외처리에 해당되지 않으면, 유효한 다음 좌표를 큐에 추가한다.

 

                q.add(new int[] {nextX, nextY});

 

6. 최단 거리 저장

 

배열 arr에는 최단 경로를 저장함

 

                arr[nextX][nextY] = arr[currX][currY] + 1;
                isVisited[nextX][nextY] = true;

 

 

전체 코드 ▼

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

public class BOJ2178 {
    int[][] arr;
    int N, M;
    boolean[][] isVisited;

    int[] dx = {-1, 1, 0, 0}; // 상, 하
    int[] dy = {0, 0, -1, 1}; // 좌, 우

    public void solution() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        // 인접 행렬 설정 (단방향)
        arr = new int[N][M];
        for (int i = 0; i < N; i++) {
            String s = br.readLine();
            for (int j = 0; j < M; j++) {
                arr[i][j] = s.charAt(j) - '0'; // 공백 없는 문자 split 해서 받기
            }
        }

        // BFS
        Queue<int[]> q = new LinkedList<>(); // 배열도 큐로 저장 가능 !!
        q.add(new int[] {0, 0}); // 이렇게 초기화 !

        isVisited = new boolean[N][M];
        isVisited[0][0] = true;

        while (!q.isEmpty()) {
            int[] curr = q.poll();
            int currX = curr[0];
            int currY = curr[1];

            for (int i = 0; i < 4; i++) {
                int nextX = currX + dx[i];
                int nextY = currY + dy[i];

                if (nextX < 0 || nextY < 0 || nextX >= N || nextY >= M) {
                    continue;
                }

                if (isVisited[nextX][nextY] || arr[nextX][nextY] == 0) {
                    continue;
                }

                q.add(new int[] {nextX, nextY});
                arr[nextX][nextY] = arr[currX][currY] + 1;
                isVisited[nextX][nextY] = true;
            }
        }

        System.out.print(arr[N-1][M-1]);
    }

    public static void main(String[] args) throws Exception {
        new BOJ2178().solution();
    }
}