[백준] 3197번 - 백조의호수 (자바, java)

문제

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

3197번: 백조의 호수

 

문제 설명

두 백조가 며칠 만에 만날 수 있는지 찾는 문제입니다.

빙하가 존재하고 매일 물과 맞닿는 부분은 물로 변하게 됩니다.

 

주의할 점

1. 백조는 물 위에 존재한다.

2. 백조A와 백조 B가 만날 수 있는 최소 시간이다. (백조 사이의 최소 거리가 아님)

 

문제풀이

2가지 방법으로 접근할 수 있습니다.

1. BFS

2. union-find(문제 해결 방법에 대해서만 설명하겠습니다.)

 

1. BFS

우리는 문제에서 주어진 것을 다음과 같은 반복문을 통하여 해결할 수 있습니다.

1. 두 백조가 만날 수 있는지 확인

  - 만날 수 있다면 day 리턴하고 반복문 빠져나오기

2. 빙하 녹이기

3. day++

while (true) {
    // 백조 인접 여부 확인
    if (check()) {
        System.out.println(day);
        break;
    }
    //빙하 녹이기(물 확산)
    melt();
    day++;
}

 

 

 

1. 두 백조가 만날 수 있는지 확인

문제 난이도를 보면 알 수 있듯이 단순히 BFS을 이용하면 해결할 수 없습니다.

그 이유는 데이터의 크기를 보면 알 수 있습니다.

그래프의 크기는 1500*1500입니다.

만약 백조가 양쪽 끝에 있다면 약 1000번 만에 만날 수 있습니다.

따라서 연산 횟수는 1500*1500*1000 => 22억 5천 => 22초(시간초과)

 

그래서 우리는 조금 더 이를 단순화할 필요가 있습니다.

어떻게 단순화하냐면. BFS을 돌릴 때 만난 빙하를 큐에 넣는다.

다음 BFS은 빙하가 들어있는 큐를 기준으로 BFS을 돌린다.

 

Queue<Node> newQ = new ArrayDeque<>();
while (!Q.isEmpty()) {

    int size = Q.size();
    while (size-- > 0) {
        Node cur = Q.poll();
        int x = cur.x;
        int y = cur.y;

        if (cur.x == end.x && cur.y == end.y) {
            return true;
        }


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

            if (isOut(nx, ny) || visited[nx][ny]) {
                continue;
            }

            visited[nx][ny] = true;
            if (G[nx][ny] == 'X') {
                newQ.add(new Node(nx, ny));
                continue;
            }
            Q.add(new Node(nx, ny));
        }

    }
}
Q = newQ;

 

2. 빙하 녹이기

빙하는 상하좌우로 물이 있을 경우 녹습니다. 따라서 처음에 물을 큐 water에 넣고 상하좌우에 물이 있으면 새로운 큐 newQ에 넣습니다. newQ는 다음 날 가장자리에 있는 물이 됩니다.

 

static void melt() {
    Queue<Node> melting = new ArrayDeque<>();

    while (!water.isEmpty()) {
        Node cur = water.poll();
        int x = cur.x;
        int y = cur.y;


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

            if (isOut(nx, ny) || G[nx][ny] != 'X') {
                continue;
            }

            G[nx][ny] = '.';
            melting.add(new Node(nx, ny));
        }
    }
    water = melting;
}

 

전체코드

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

public class Main {

    static class Node {
        int x;
        int y;

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


    // 백조 인접 여부
    static boolean check() {


        Queue<Node> newQ = new ArrayDeque<>();
        while (!Q.isEmpty()) {

            int size = Q.size();
            while (size-- > 0) {
                Node cur = Q.poll();
                int x = cur.x;
                int y = cur.y;

                if (cur.x == end.x && cur.y == end.y) {
                    return true;
                }


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

                    if (isOut(nx, ny) || visited[nx][ny]) {
                        continue;
                    }

                    visited[nx][ny] = true;
                    if (G[nx][ny] == 'X') {
                        newQ.add(new Node(nx, ny));
                        continue;
                    }
                    Q.add(new Node(nx, ny));
                }

            }
        }
        Q = newQ;
        return false;

    }

    static boolean isOut(int x, int y) {
        if (x < 0 || y < 0 || x >= R || y >= C) {
            return true;
        }
        return false;

    }


    static void melt() {
        Queue<Node> melting = new ArrayDeque<>();

        while (!water.isEmpty()) {
            Node cur = water.poll();
            int x = cur.x;
            int y = cur.y;


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

                if (isOut(nx, ny) || G[nx][ny] != 'X') {
                    continue;
                }

                G[nx][ny] = '.';
                melting.add(new Node(nx, ny));
            }
        }
        water = melting;
    }

    static Node start, end;
    static Queue<Node> Q;
    static Queue<Node> water;
    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};
    static boolean[][] visited;
    static int R, C;
    static char[][] G;

    public static void main(String[] args) throws Exception {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st = new StringTokenizer(br.readLine());
        R = Integer.parseInt(st.nextToken());
        C = Integer.parseInt(st.nextToken());
        visited = new boolean[R][C];
        G = new char[R][C];

        water = new ArrayDeque<>();
        Q = new ArrayDeque<>();


        for (int i = 0; i < R; i++) {
            G[i] = br.readLine().toCharArray();
            for (int j = 0; j < C; j++) {
                if (G[i][j] == 'L') {
                    if (start == null) {
                        start = new Node(i, j);
                        visited[i][j] = true;
                        Q.add(new Node(i, j));
                    } else {
                        end = new Node(i, j);
                    }
                    water.add(new Node(i, j));
                } else if (G[i][j] == '.') {
                    water.add(new Node(i, j));
                }
            }
        }


        int day = 0;

        while (true) {
            // 백조 인접 여부 확인
            if (check()) {
                System.out.println(day);
                break;
            }
            //빙하 녹이기(물 확산)
            melt();
            day++;
        }

    }
}

 

결과

 

2. union-find을 이용한 문제 예시

주어진 3번 예시를 다음과 같이 볼 수 있습니다.

각각의 물이 뭉쳐 있는 집합을 이용하여 

union-find(disjoint-set)을 이용하여 문제를 해결할 수 있습니다.

A백조와 B백조가 같은 area 번호라면 둘은 만날 수 있습니다. 

물을 area로 나타낸 그림