[JAVA] 3197 - 백조의 호수 💚5 : 방문배열 대신 Queue를 여러개 사용하여 탐색범위를 지정하자. (BFS + 플러드필)

들어가며

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

물(.)과 인접한 얼음(X)는 매초마다 녹는다. 백조(L)은 물(.)로 이동할 수 있고 매초마다 만날 수 있는지 없는지 확인하여 며칠이 지나야 백조가 서로 만날 수 있는지 출력하면 된다.

본문으로

플레 탐색 문제라 처음에 살짝 쫄고(?) 들어갔다. 처음에는 백조(L)가 물(.)을 재귀적으로 계속 탐색하면 되겠다 싶어서 DFS로 재귀적으로 탐색하며 백조를 찾게끔 하였다. 첫번째 풀이는 아래와 같다.

public class Main {

    static int Y;
    static int X;
    static char[][] maps;
    static int[][] visited;
    static int[][] visitedBird;
    static int[] dy = {-1, 0, 1, 0};
    static int[] dx = {0, 1, 0, -1};
    static int turn;
    static boolean ok;
    static List<Node> startPoints;
    static Node bird;

    static class Node {
        int y;
        int x;

        Node(int y, int x) {
            this.y = y;
            this.x = x;
        }
    }

    static void go(int y, int x) {
        visitedBird[y][x] = 1;
        for (int i = 0; i < 4; i++) {
            int ny = y + dy[i];
            int nx = x + dx[i];
            if (ny < 0 || nx < 0 || ny >= Y || nx >= X || visitedBird[ny][nx] != 0) {
                continue;
            }
            if (maps[ny][nx] == 'L') {
                ok = true;
                return;
            }
            if (maps[ny][nx] == '.') {
                go(ny, nx);
            }
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(bf.readLine());
        Y = Integer.parseInt(st.nextToken());
        X = Integer.parseInt(st.nextToken());

        maps = new char[Y][X];
        visited = new int[Y][X];
        startPoints = new ArrayList<>();

        for (int i = 0; i < Y; i++) {
            String line = bf.readLine();
            for (int j = 0; j < X; j++) {
                char input = line.charAt(j);
                if (input == '.') {
                    startPoints.add(new Node(i, j));
                }
                if (input == 'L') {
                    bird = new Node(i, j);
                }
                maps[i][j] = input;
            }
        }

        ArrayDeque<Node> queue = new ArrayDeque<>();
        for (int i = 0; i < startPoints.size(); i++) {
            Node node = startPoints.get(i);
            queue.add(new Node(node.y, node.x));
            visited[node.y][node.x] = 1;
        }
        turn = 1;
        ok = false;

        while (!queue.isEmpty()) {
            int qSize = queue.size();
            for (int i = 0; i < qSize; i++) {
                Node front = queue.poll();
                for (int j = 0; j < 4; j++) {
                    int ny = front.y + dy[j];
                    int nx = front.x + dx[j];

                    if (ny < 0 || nx < 0 || ny >= Y || nx >= X || visited[ny][nx] != 0) {
                        continue;
                    }
                    if (maps[ny][nx] == 'X') {
                        maps[ny][nx] = '.';
                        visited[ny][nx] = visited[front.y][front.x] + 1;
                        queue.add(new Node(ny, nx));
                    }
                }
            }
            visitedBird = new int[Y][X];
            go(bird.y, bird.x);
            if (ok) {
                break;
            }
            turn++;
        }

        System.out.println(turn);
    }
}

풀이는 좀 길어졌지만 간단하게, 플러드필을 적용해서 얼음을 한 턴에 녹이는 것을 qSize로 상수화 시키면서 turn++ 하며 백조가 만날 수 있는지 없는지를 DFS로 확인했다.. 문제에서 제공되는 4개의 예시는 잘 출력된다. 원트에 플레문제 푼 듯 하여 싱글벙글 제출했는데?!

시간초과가 난다..ㅎㅎ 역시 이렇게 쉽게 풀리면 플레가 아니지..

매턴마다 DFS의 재귀적 흐름을 제어하기 위해서는 방문배열을 초기화했어야 했는데, 이 부분이 시간초과의 원인이었다. 매턴마다 Y, X ≤ 1500 → 최대 2,250,000 칸을 초기화하며 DFS로 모든 물을 탐색중이었던 것이다..

 

• 턴 수가 O(YX) 수준
• 매 턴 DFS가 O(YX)
• 총 시간복잡도는 거의 O((YX)²)

정리하고 나니 시간초과가 터질 수밖에 없는 코드였나 싶다...

---

그러면 방문배열을 매번 초기화를 하지 않고 재귀적흐름을 제어하고, 저번턴에 갔던 곳을 안 갈 수가 있을까? 고민 끝에 제출한 코드는 아래와 같다.

public class Main {

    static int[] dy = {-1, 0, 1, 0};
    static int[] dx = {0, 1, 0, -1};

    static int Y;
    static int X;
    static char[][] maps;
    static int[][] visited;
    static Node swan;
    static ArrayDeque<Node> swanQ;
    static ArrayDeque<Node> nextSwanQ;
    static ArrayDeque<Node> waterQ;
    static int day;

    static class Node {
        int y;
        int x;

        Node(int y, int x) {
            this.y = y;
            this.x = x;
        }
    }

    static boolean swanMeet() {
        while (!swanQ.isEmpty()) {
            Node front = swanQ.poll();
            for (int i = 0; i < 4; i++) {
                int ny = front.y + dy[i];
                int nx = front.x + dx[i];

                if (nx < 0 || ny < 0 || ny >= Y || nx >= X || visited[ny][nx] != 0) {
                    continue;
                }

                visited[ny][nx] = 1;
                if (maps[ny][nx] == '.') {
                    swanQ.add(new Node(ny, nx));
                } else if (maps[ny][nx] == 'X') {
                    nextSwanQ.add(new Node(ny, nx));
                } else if (maps[ny][nx] == 'L') {
                    return true;
                }
            }

        }
        return false;
    }

    static ArrayDeque<Node> melt() {
        ArrayDeque<Node> queue = new ArrayDeque<>();

        while (!waterQ.isEmpty()) {
            Node front = waterQ.poll();
            for (int i = 0; i < 4; i++) {
                int ny = front.y + dy[i];
                int nx = front.x + dx[i];

                if (ny < 0 || nx < 0 || ny >= Y || nx >= X) {
                    continue;
                }

                if (maps[ny][nx] == 'X') {
                    maps[ny][nx] = '.';
                    queue.add(new Node(ny, nx));
                }
            }
        }
        return queue;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(bf.readLine());

        Y = Integer.parseInt(st.nextToken());
        X = Integer.parseInt(st.nextToken());

        maps = new char[Y][X];
        visited = new int[Y][X];
        waterQ = new ArrayDeque<>();

        for (int i = 0; i < Y; i++) {
            String line = bf.readLine();
            for (int j = 0; j < X; j++) {
                char input = line.charAt(j);
                if (input != 'X') {
                    waterQ.add(new Node(i, j));
                }
                if (input == 'L') {
                    swan = new Node(i, j);
                }
                maps[i][j] = input;
            }
        }

        day = 0;
        swanQ = new ArrayDeque<>();
        nextSwanQ = new ArrayDeque<>();
        swanQ.add(swan);
        visited[swan.y][swan.x] = 1;
        while (true) {
            if (swanMeet()) {
                System.out.println(day);
                break;
            }

            waterQ = melt();

            swanQ = nextSwanQ;
            nextSwanQ = new ArrayDeque<>();
            day++;

        }
    }
}

보면 알 수 있다시피 방문배열을 매번 초기화시키지 않고, 다음에 탐색할 곳만 큐에 담아놓기 위해서 다음에 백조가 탐색할 곳은 nextSwanQ에 담고, 다음 녹일 곳을 탐색하기 위해서 melt() 메서드에서 물과 맟닿아 있는 얼음만 큐에 담은 다음에 그 큐를 반환해서 사용중이다. 즉 큐를 여러개 사용하여 다음에 탐색할 곳을 계속 최신화 시켜주는 것이다!

이렇게 원하는 곳을 색칠하면서 탐색하는 것이 플러드필인데, 큐를 여러개 사용하는 방식이 정석이라고도 한다.

 

마무리하며

요즘 BFS를 깊게 파고 있는데 수준이 올라가는 방식의 BFS문제들은 보통 방문 방식이 달라진다거나, 그 방법의 갯수나 방법을 저장해야한다거나... 원하는 영역만 탐색하게 한다거나(플러드필) 등등의 방식으로 문제를 심화시키는 것 같다. 당황하지 말고 그 부분만 잘 고려하면 로직은 대부분 비슷한 것 같다!! 연습만이 살길이다! 계속 정진하자.