[JAVA] 백준 2178. 미로 탐색 (BFS) :: 로직/코드 - GODZ

안녕하세요 GODZ입니다.

오늘은 BFS를 이용한 문제를 풀어볼 예정입니다.

 

---

1. 문제

 

2. 입출력 예제

 

3. 접근

1. 지도 정보를 담을 2차원 배열 생성합니다.

2. 시작이 (0,0) 이 아닌 (1,1) 이기 때문에 개인적으로 인덱스에 대한 혼동이 오지 않도록 (N+1) x (M+1) 크기로 만들었습니다.

3. 좌표를 큐에 저장할 때는 클래스로 만드는 게 편리합니다.

4. 상/하/좌/우 인접한 좌표로 이동할 수 있기 때문에 해당 좌표가 방문했던 곳인지 아닌지를 판단하기 위해 같은 크기의 2차원 배열이 필요합니다.

5. 상/하/좌/우에 대해 검사할 때는 dx(상하좌우 각각에 대한 x좌표 변경값), dy(상하좌우 각각에 대한 y좌표 변경값)의 배열을 만들어 반복문을 통해 체크합니다.

6. 5번의 경우 dx, dy 배열을 만드는 이유는 혹시 문제에서 대각선까지 고려해야하는 경우, 이 방법이 편리하다고 생각하기 때문입니다.

7. 최단거리에 대한 변수 지정 방법에는 여러가지가 있을거라고 생각합니다. 저는 특정 좌표에 방문할 때 (1,1)에서부터의 거리를 또 다른 배열에 저장해주면서 (N,M)에 도달하는 방식을 사용했습니다.

 

4. 로직

1. (1,1) 좌표 객체를 큐에 넣습니다.

2. (1,1) 방문값을 true로, (1,1)까지의 거리는 1로 설정합니다. (초기값)

3. poll() 을 호출하여 좌표 객체를 꺼냅니다. (i0, j0)

4. 좌표 객체 (i0, j0)의 상/하/좌/우를 확인합니다.

5. 지도의 밖을 벗어나지 않고, 지도의 값이 1이고, 방문값이 false인 경우, (i1, j1)를 큐에 넣습니다.

6. (i1, j1) 방문값을 true로, (i1, j1)까지의 거리는 (i0, j0)까지의 거리 + 1로 설정합니다.

7. 4로 돌아가 남은 방향도 검사합니다. 방향을 모두 검사했으면 3으로 돌아갑니다. 꺼낼 좌표 객체가 없으면 종료합니다.

 

5. 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.StringTokenizer;
 
class Pos {
    int nPos;
    int mPos;
    public Pos(int n, int m) {
        this.nPos = n;
        this.mPos = m;
    }
}
 
public class Main {
    static int N;
    static int M;
    static int[] dirN = {-1, 1, 0, 0};    // 상,하,좌,우 순서
    static int[] dirM = {0, 0, -1, 1};    // 상,하,좌,우 순서
    static int[][] map;
    static int[][] dist;
    static boolean[][] visited;
    static LinkedList<Pos> queue;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine().trim());
        
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        
        map = new int[N+1][M+1];
        dist = new int[N+1][M+1];        
        visited = new boolean[N+1][M+1];
        queue = new LinkedList<>();
        
        for(int i = 1; i <= N; i++) {
            st = new StringTokenizer(br.readLine().trim());
            String s = st.nextToken().toString();
            for(int j = 1; j <= M; j++) {
                map[i][j] = s.charAt(j-1) - '0';
            }
        }
        
        solveBFS();
        System.out.println(dist[N][M]);
    }
 
    private static void solveBFS() {
        queue.add(new Pos(1, 1));
        dist[1][1] = 1;
        visited[1][1] = true;
        while(!queue.isEmpty()) {
            Pos currPos = queue.poll();
            for(int i = 0; i < 4; i++) {
                Pos nextPos = new Pos(currPos.nPos + dirN[i], currPos.mPos + dirM[i]);
                if(boundaryCheck(nextPos) && !visited[nextPos.nPos][nextPos.mPos]) {
                    queue.add(nextPos);
                    dist[nextPos.nPos][nextPos.mPos] = dist[currPos.nPos][currPos.mPos] + 1;
                    visited[nextPos.nPos][nextPos.mPos] = true;
                }
            }
        }
    }
 
    private static boolean boundaryCheck(Pos pos) {
        boolean res = true;
        if(pos.nPos <= 0 || pos.mPos <= 0 || pos.nPos > N || pos.mPos > M) {
            res = false;
        } else if(map[pos.nPos][pos.mPos] == 0) {
            res = false;
        }
        return res;
    }
}

 

6. 결과