[BOJ] 3197 백조의 호수 (Java)

1. 문제요약

3197번: 백조의 호수 (acmicpc.net)

3197번: 백조의 호수

R x C 직사각형 모양의 호수가 존재한다. 이 호수에는 백조가 두 마리 존재하는데 빙판이 있어 서로 만날 수 없다. 하루가 지날 때마다 물에 인접한 빙판들은 모두 녹는다고 할 때 며칠이 지나야 백조 두 마리가 만날 수 있는지 구하시오.

 

2. 문제예제

 

3. 문제풀이(수동)

전형적인 BFS 문제로 수동 풀이는 진행하지 않는다. 지문에서 언급한 내용처럼 물에 인접한 빙판들은 모두 녹는다.

녹을 때 두 백조가 만날 수 있는지만 체크하면 된다.

 

 

4. 팩트추출

Fact 1 : 전형적인 BFS 문제이다. 한 번 맵을 훑으면서 빙판을 녹이고, 백조가 서로 만나는지 다시 맵을 훑으면 된다. 단순 BFS 구현 문제라고 생각이 들지만, R 과 C 가 무려 1500 으로 한 번 맵을 탐색할 때마다 1500 * 1500 시간복잡도가 발생한다. 그것도 빙판을 녹일 때 한 번, 백조가 서로 만나는지 확인하기 위해 한 번 수행하면 총 1500 * 1500 * 2 시간복잡도가 된다. 조금 더 효과적으로 BFS 를 수행해야 한다.

 

Fact 2 : 백조 중심으로 BFS 를 수행하면 빙판을 만나거나 백조를 만나거나 두 가지 경우를 만나게 된다. 백조를 만나면 그 동안에 계산된 day 를 리턴하면 되고, 빙판을 만났다면 그 빙판들을 기억하기 위해 모두 큐에 담아 그 큐에서부터 다시 시작하면 된다. 빙판을 녹이기 위한 BFS 는 따로 수행해서 서로 영향을 미치지 않게 동작시킨다. 따라서, Water 에 대한 큐, 다음 검색을 위한 큐가 필요하다.

 

5. 문제전략

문제 전략은 팩트 추출을 통해 알아보았다. 백조 중 하나부터 시작해서 dfs 를 수행하고 빙판을 만나면 그 지점들을 기억했다가 다시 그 부분부터 dfs 를 시작하면 된다. 다시 dfs 를 시작하기 전 빙판이 녹아야 하므로 빙판에 대한 dfs 를 한 번 수행한다.

 

6. 소스코드

package org.example;

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

public class Main {
    private static int R, C;
    private static Node[] swan;
    private static char[][] map;
    private static Queue<Node> queue, waterQueue;
    private static boolean[][] visited;
    private static final int[] dr = { -1, 1, 0, 0 };
    private static final int[] dc = { 0, 0, -1, 1 };
    private static int day = 0;
    static class Node {
        int r, c;
        Node(int r, int c) {
            this.r = r;
            this.c = c;
        }
    }
    private static void waterBFS() {
        // 한 번만 녹여야 하므로, 현재 큐 사이즈만큼만 돌린다.
        int waterSize = waterQueue.size();
        while (waterSize-- > 0) {
            Node now = waterQueue.poll();
            for (int i = 0; i < 4; i++) {
                int nextR = now.r + dr[i];
                int nextC = now.c + dc[i];
                if (nextR >= R || nextR < 0 || nextC >= C || nextC < 0) continue;
                if (map[nextR][nextC] == 'X') {
                    map[nextR][nextC] = '.';
                    waterQueue.offer(new Node(nextR, nextC));
                }
            }
        }
    }
    private static void BFS() {
        boolean meet = false;
        while (true) {
            Queue<Node> nextQueue = new LinkedList<>();
            while (!queue.isEmpty()) {
                Node now = queue.poll();
                if (now.r == swan[1].r && now.c == swan[1].c) {
                    meet = true;
                    break;
                }
                for (int i = 0; i < 4; i++) {
                    int nextR = now.r + dr[i];
                    int nextC = now.c + dc[i];
                    if (nextR >= R || nextR < 0 || nextC >= C || nextC < 0 || visited[nextR][nextC]) continue;
                    visited[nextR][nextC] = true;
                    if (map[nextR][nextC] == 'X') {
                        nextQueue.offer(new Node(nextR, nextC));
                        continue;
                    }
                    queue.offer(new Node(nextR, nextC));
                }
            }
            if (meet) break;
            queue = nextQueue;
            waterBFS();
            day++;
        }
        return;
    }

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

        R = Integer.parseInt(st.nextToken());
        C = Integer.parseInt(st.nextToken());

        map = new char[R][C];
        swan = new Node[2];
        queue = new LinkedList<>();
        waterQueue = new LinkedList<>();
        visited = new boolean[R][C];

        int swanIndex = 0;
        for (int i = 0; i < R; i++) {
            char[] line = br.readLine().toCharArray();
            for (int j = 0; j < C; j++) {
                map[i][j] = line[j];
                if(map[i][j] == 'L') {
                    swan[swanIndex++] = new Node(i, j);
                }
                if(map[i][j] != 'X') {
                    waterQueue.offer(new Node(i, j));
                }
            }
        }
        queue.offer(swan[0]);
        visited[swan[0].r][swan[0].c] = true;
        BFS();
        System.out.println(day);
    }
}