[Algorithm] 백준 2206 BFS 자바 풀이

안녕하세요. 회사와 함께 성장하고 싶은 KOSE입니다.

 

이번 포스팅은 BFS의 2206번 자바 풀이를 작성하고자 합니다.

BFS는 Queue를 활용하기 때문에 선입 선출로 처리되며 최단 거리를 찾는데 효율적입니다.

 

문제 링크: https://www.acmicpc.net/problem/2206

2206번: 벽 부수고 이동하기

 

 

1. 코드

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

import java.util.ArrayDeque;
import java.util.Queue;

import static java.lang.Integer.parseInt;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] inputs = br.readLine().split(" ");

        int n = parseInt(inputs[0]);
        int m = parseInt(inputs[1]);

        WallMap wallMap = new WallMap(n, m);
        for (int i = 0; i < n; i++) {
            String str = br.readLine();
            for (int j = 0; j < m; j++) {
                wallMap.addMap(i, j, str.charAt(j));
            }
        }

        System.out.println(wallMap.findShortRoad());
    }
}

class WallMap {

    static final int[] D_X = {1, 0, -1, 0};
    static final int[] D_Y = {0, 1, 0, -1};

    char[][] map; // 입력한 벽을 저장할 2차원 배열
    boolean[][][] visited; // 방문 여부 3차원 배열

    class Road {
        int x; // x 좌표
        int y; // y 좌표
        int step; // bfs 단계
        boolean destroyed; // 길에 벽이 있다면 파괴 여부

        Road(int x, int y, int step, boolean destroyed) {
            this.x = x; 
            this.y = y;
            this.step = step;
            this.destroyed = destroyed;
        }

    }

    WallMap(int n, int m) {
        map = new char[n][m];
        visited = new boolean[n][m][2];
    }

    void addMap(int x, int y, char c) {
        map[x][y] = c;
    }
 
    int findShortRoad() {
        Queue<Road> queue = new ArrayDeque<>(); // 큐 생성
        queue.add(new Road(0, 0, 1, false)); // 첫 번째 길 등록 (x = 0, y = 0, step = 1, 파괴 X)

        // bfs
        while(!queue.isEmpty()) {
            Road road = queue.poll(); // 큐에서 저장한 Road 인스턴스 빼기

            if (road.x == map.length - 1 && road.y == map[0].length - 1) {
                return road.step; // 만약 찾아야 하는 마지막 배열에 위치한 경우 종료
            }

            for (int k = 0; k < D_X.length; k++) {
                int newX = road.x + D_X[k]; // dx dy 
                int newY = road.y + D_Y[k];

                if (validRange(newX, newY)) continue; // 인덱스 유효한 배열 확인

                if (map[newX][newY] == '0') { // 만약 map에 있는 값이 벽이 아니라면
                    if (!road.destroyed && !visited[newX][newY][0]) {
                        
                        // 큐에 new Road()로 새로운 길의 x, y, step + 1, 벽 파괴 X 입력하기
                        queue.add(new Road(newX, newY, road.step + 1, false));
                        visited[newX][newY][0] = true; // 방문 여부 등록
                    }

                    // 만약 길이 파괴된 상태, 방문하지 않은 경우 true를 queue에 넣기
                    else if (road.destroyed && !visited[newX][newY][1]) {
                        queue.add(new Road(newX, newY, road.step + 1, true));
                        visited[newX][newY][1] = true;
                    }
                }

                // 만약 새로운 길이 벽이라면, 파괴되지 않은 경우만 큐에 넣기
                else if (map[newX][newY] == '1') {
                    if (!road.destroyed) {
                        queue.add(new Road(newX, newY, road.step + 1, true));
                        visited[newX][newY][1] = true;
                    }
                }
            }
        }
        return -1;
    }

    boolean validRange(int x, int y) {
        return x < 0 || y < 0 || x >= map.length || y >= map[0].length;
    }


}

 

 

 

2. 풀이 중 어려웠던 점

 

이전 BFS 문제를 해결할 때는 인스턴스 배열을 생성해서 그 안에 인스턴스를 넣고 초기화하는 작업을 수행했습니다. 만약 입력 시점에 1이 입력된다면 possibleBreakWall 리스트에 추가하는 방법을 했습니다.

 

하지만, 시간초과가 발생했고 비효율적인 방법이었다는 점을 확인했습니다. 만약, Road 배열을 선언하고 그 안에 road 인스턴스를 넣는다면 벽을 깬 방법이 올바르지 않을 때, 매번 배열에 등록된 인스턴스를 전부 초기화하는 작업을 수행했어야 했습니다.

 

class WallMap {

    Road[][] roads;
    List<Road> possibleBreakWall = new ArrayList<>();

 

이 문제를 해결하기 위해,

따라서, char[][] map이라는 배열을 등록하여, Queue에 넣을 때마다 인스턴스에 상태를 기록하는 방법을 적용했습니다.

 

이 방법의 장점은

BFS는 계속 순회하되, map이라는 벽을 기록한 상태 정보는 바뀌지 않기 때문에
Queue에 등록되는 인스턴스의 벽을 깼는지 여부를 파악하고 다음 스텝에 새로운 Road 인스턴스를 생성하며 현재 스텝 + 1, 벽 깬 여부 true만 이어서 등록하면 됩니다.

 

즉, Queue에 있는 road는 해당 좌표와 현재 벽을 깼는지 그리고 방문한 상태인지만 파악한다면 

1 -> 2 -> 3(벽 깸)  ->  5  ->  7 (벽 못깸)

           -> 4          ->  6   ->  7(벽 깸)  -> 도착지

           -> 9(벽 깸)  -> 4 이미 2번 노드의 자식 노드인 4번 노드에서 먼저 방문 했으므로 종료

 

이런식으로 처리 될 수 있습니다.

 

이상입니다!! 감사합니다!!