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

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

Problem

제출일 : 2020-05-06

문제 풀이 시간 : 3H

난이도 : ★★★★

---

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

두 마리의 백조가 호수에서 살고 있었다. 그렇지만 두 마리는 호수를 덮고 있는 빙판으로 만나지 못한다.

호수는 가로로 R, 세로로 C만큼의 직사각형 모양이다. 어떤 칸은 얼음으로 덮여있다.

호수는 차례로 녹는데, 매일 물 공간과 접촉한 모든 빙판 공간은 녹는다. 두 개의 공간이 접촉하려면 가로나 세로로 닿아 있는 것만 (대각선은 고려하지 않는다) 생각한다.

아래에는 세 가지 예가 있다.

...XXXXXX..XX.XXX ....XXXX.......XX .....XX.......... 
....XXXXXXXXX.XXX .....XXXX..X..... ......X.......... 
...XXXXXXXXXXXX.. ....XXX..XXXX.... .....X.....X..... 
..XXXXX..XXXXXX.. ...XXX....XXXX... ....X......XX.... 
.XXXXXX..XXXXXX.. ..XXXX....XXXX... ...XX......XX.... 
XXXXXXX...XXXX... ..XXXX.....XX.... ....X............ 
..XXXXX...XXX.... ....XX.....X..... ................. 
....XXXXX.XXX.... .....XX....X..... ................. 
      처음               첫째 날             둘째 날

백조는 오직 물 공간에서 세로나 가로로만(대각선은 제외한다) 움직일 수 있다.

며칠이 지나야 백조들이 만날 수 있는 지 계산하는 프로그램을 작성한다.

Input

입력의 첫째 줄에는 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1500.

각 R줄 동안 C만큼의 문자열이 주어진다.

'.'은 물 공간, 'X'는 빙판 공간, 'L'은 백조가 있는 공간으로 나타낸다.

Output

첫째 줄에 문제에서 주어진 걸리는 날을 출력한다.

Example

input

8 17
...XXXXXX..XX.XXX
....XXXXXXXXX.XXX
...XXXXXXXXXXXX..
..XXXXX.LXXXXXX..
.XXXXXX..XXXXXX..
XXXXXXX...XXXX...
..XXXXX...XXX....
....XXXXX.XXXL...

output

2

Solution & Inpression

시간초과로 문제 해결이 어려웠던 문제이다.

단순히 BFS로 문제를 구현하는 것 이상의 아이디어가 필요했다.

어려웠던 문제로 블로그의 글을 참고해 문제를 해결하였습니다.

Code

언어 : JAVA

메모리 : 215728 kb

실행 시간 : 1012 ms

package BOJ.DFS_BFS;
import java.awt.Point;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Gold1_3197_백조의호수 {
    static int R, C;
    static char[][] map;
    static Point[] swan;

    static int[] dr = { -1, 1, 0, 0 };
    static int[] dc = { 0, 0, -1, 1 };

    static Queue<int[]> swanQ;
    static Queue<int[]> waterQ;

    static boolean[][] visit_swan;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        R = sc.nextInt();
        C = sc.nextInt();

        map = new char[R][C];
        swan = new Point[2];

        swanQ = new LinkedList<>();
        visit_swan = new boolean[R][C];

        waterQ = new LinkedList<>();

        // 데이터 입력
        int index = 0;
        for (int i = 0; i < R; ++i) {
            String line = sc.next();
            for (int j = 0; j < C; ++j) {
                map[i][j] = line.charAt(j);
                if (map[i][j] == 'L') {
                    map[i][j] = '.';
                    swan[index++] = new Point(i, j);
                }
                if (map[i][j] == '.') {
                    waterQ.add(new int[] { i, j });
                }
            }
        }

        // 출발점이 되는 백조
        swanQ.add(new int[] { swan[0].x, swan[0].y });
        visit_swan[swan[0].x][swan[0].y] = true;

        int day = 0;
        while (true) {
            if (move_swan())
                break;
            melt();
            day++;
        }

        System.out.println(day);
    }

    private static boolean move_swan() {
        Queue<int[]> nextQ = new LinkedList<>();
        while (!swanQ.isEmpty()) {
            int[] now = swanQ.poll();

            if (now[0] == swan[1].x && now[1] == swan[1].y) {
                return true;
            }

            for (int k = 0; k < 4; ++k) {
                int nr = now[0] + dr[k];
                int nc = now[1] + dc[k];

                if (!isRange(nr, nc) || visit_swan[nr][nc])
                    continue;
                visit_swan[nr][nc] = true;
                if (map[nr][nc] == '.') {
                    swanQ.add(new int[] { nr, nc });
                }
                // 다음날 얼음이 녹아 백조가 지나 갈 수 있음.
                else if (map[nr][nc] == 'X') {
                    nextQ.add(new int[] { nr, nc });
                }
            }
        }
        // q를 다음날 탐색할 지역이 담긴 nextQ로 바꾼다.
        swanQ = nextQ;
        return false;
    }

    private static void melt() {
        // 얼음을 녹인다.
        int size = waterQ.size();
        for (int i = 0; i < size; ++i) {
            int[] now = waterQ.poll();

            for (int k = 0; k < 4; ++k) {
                int nr = now[0] + dr[k];
                int nc = now[1] + dc[k];

                if (isRange(nr, nc) && map[nr][nc] == 'X') {
                    map[nr][nc] = '.';
                    waterQ.add(new int[] { nr, nc });
                }
            }
        }
    }

    private static boolean isRange(int nr, int nc) {
        if (0 <= nr && nr < R && 0 <= nc && nc < C)
            return true;
        return false;
    }
}

Reference

https://velog.io/@hyeon930/BOJ-3197-%EB%B0%B1%EC%A1%B0%EC%9D%98-%ED%98%B8%EC%88%98-Java