Q. 3197 자바 : 백조의 호수

Q. 3197 자바 : 백조의 호수

 

문제 : boj.kr/3197

P5 난이도의 문제이다.

 

문제를 간단히 설명하자면

얼음, 물, 백조가 있고, 물과 인접한 얼음은 시간이 지날 때 마다 물로 변한다.

백조는 물이 있는 영역으로만 지나다닐 수 있을 때, 두 백조가 만날 수 있는 최소 시간은 몇초인지 구하는 문제이다.

---

먼저 완전 탐색 방식으로 푼다고 가정하면 아래와 같이 풀었을 것 같다.

1. 물 근처의 얼음을 완전탐색을 활용해 녹인다.

2. 녹인 후 백조가 만날 수 있는지 계산한다.

3. 만약 백조가 만날 수 없다면 1, 2번 과정을 반복한다.

 

이렇게 푼다면 R, C의 범위가 1500이므로 R^2 * C^2의 시간복잡도를 가지고,

시간제한은 2초이므로 이 방법은 불가능해 보였다.

그래서 완전 탐색이 아닌 다른 방법을 생각해야 한다.

---

이 문제에서 중요한 점은 이미 계산한 내용을 다시 계산하고 있지 않은지? 를 확인하는 것 이다.

 

처음에는 물과 인접한 얼음을 녹여야겠지만, 이후에는 녹은 얼음과 인접한 얼음만 계산하면 된다는 점과이전 날에 백조가 만나기 위해 방문했던 영역은 다시 계산할 필요가 없다는 점 이다.

 

이를 참고해 아래와 같은 방식으로 풀었고, 시간 복잡도는 O(2 * R * C)이다.

 

1.canMeet -  백조가 만날 수 있는지 -> O(R * C)

BFS를 사용해 백조가 서로 만날 수 있는지 계산한다.

만약 백조를 만나지 못한 경우, 백조가 막혔던 빙하의 위치를 저장하고 다음 탐색 시 해당 위치부터 시작한다.

 

2. melt - 빙하 녹이기 -> O(R * C)

큐에 저장된 빙하의 위치에서 BFS를 통해, 물과 인접한 빙하를 찾는다.

녹은 빙하는 '.'으로 변경하고, 인접한 빙하를 저장하고 다음 빙하를 녹일 때 활용한다.

import java.io.*;
import java.util.*;

class Main {

    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringBuffer sb = new StringBuffer();
    static StringTokenizer st;
    static int r, c, day;
    static char[][] map;
    static boolean[][] visit, swanVisit;
    static int[][] swans;

    static ArrayList<int[]> meltList;
    static Queue<int[]> prevMeltQue, nextSwanQue;

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

    static void input() throws IOException{

        st = new StringTokenizer(br.readLine());
        r = Integer.parseInt(st.nextToken());
        c = Integer.parseInt(st.nextToken());

        map = new char[r][c];
        swanVisit = new boolean[r][c];
        visit = new boolean[r][c];
        meltList = new ArrayList<>();
        nextSwanQue = new ArrayDeque<>();

        int swanCnt = 0;
        swans = new int[2][2];
        for (int i = 0; i < r; i++) {
            char[] str = br.readLine().toCharArray();
            for (int j = 0; j < c; j++) {
                map[i][j] = str[j];
                if (str[j] == 'L') {
                    map[i][j] = '.';
                    swans[swanCnt++] = new int[] {i, j};
                }

                if (map[i][j] == '.') {
                    meltList.add(new int[] {i, j});
                }
            }
        }
    }

    static void pro() {

        while (!canMeet()) {
            melt();
            day++;
        }

        System.out.println(day);
    }

    static void init() {
        nextSwanQue.add(new int[] {swans[0][0], swans[0][1]});
        swanVisit[swans[0][0]][swans[0][1]] = true;
    }

    static void melt() {
        prevMeltQue = new ArrayDeque<>(meltList);
        meltList.clear();

        while (!prevMeltQue.isEmpty()) {

            int[] cur = prevMeltQue.poll();

            for (int i = 0; i < 4; i++) {
                int ny = dy[i] + cur[0];
                int nx = dx[i] + cur[1];

                if (outOfMap(ny, nx)) continue;
                if (visit[ny][nx]) continue;

                visit[ny][nx] = true;

                if (map[ny][nx] == 'X') {
                    meltList.add(new int[] {ny, nx});
                } else {
                    prevMeltQue.add(new int[] {ny, nx});
                }
            }
        }

        for (int[] cur : meltList) {
            map[cur[0]][cur[1]] = '.';
        }
    }

    static boolean canMeet() {
        Queue<int[]> que = new ArrayDeque<>(nextSwanQue);
        nextSwanQue.clear();

        while (!que.isEmpty()) {
            int[] cur = que.poll();
            if (swanVisit[swans[1][0]][swans[1][1]]) return true;

            for (int i = 0; i < 4; i++) {
                int ny = dy[i] + cur[0];
                int nx = dx[i] + cur[1];

                if (outOfMap(ny, nx)) continue;
                if (swanVisit[ny][nx]) continue;

                if (map[ny][nx] == '.') {
                    swanVisit[ny][nx] = true;
                    que.add(new int[] {ny, nx});
                } else {
                    nextSwanQue.add(new int[] {cur[0], cur[1]});
                }
            }
        }

        return false;
    }

    static boolean outOfMap(int curY, int curX) {
        return curY < 0 || curX < 0 || curY >= r || curX >= c;
    }

    public static void main(String[] args) throws Exception{
        input();
        init();
        pro();
    }
}