(3197) 백조의 호수 (Java)

문제

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

호수는 행이 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..... .................
처음 첫째 날 둘째 날
백조는 오직 물 공간에서 세로나 가로로만(대각선은 제외한다) 움직일 수 있다.

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

입력

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

다음 R개의 줄에는 각각 길이 C의 문자열이 하나씩 주어진다. '.'은 물 공간, 'X'는 빙판 공간, 'L'은 백조가 있는 공간으로 나타낸다.

출력

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

예제 입력 1

10 2
.L
..
XX
XX
XX
XX
XX
XX
..
.L

예제 출력 1

3

예제 입력 2

4 11
..XXX...X..
.X.XXX...L.
....XXX..X.
X.L..XXX...

예제 출력 2

2

예제 입력 3

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

예제 출력 3

2

출처

Olympiad > Croatian Highschool Competitions in Informatics > 2005 > National Competition #2 - Seniors 2번

문제를 번역한 사람: baemin0103
데이터를 추가한 사람: dlbae9613

알고리즘 분류

자료 구조
그래프 이론
그래프 탐색
너비 우선 탐색
분리 집합

Solution

1 시간초과

import java.io.*;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
    public static int r, c, sx, sy;
    public static char[][] lake;
    public static boolean[][] visited;
    public static boolean[][] melted;
    public static class Node {
        int x, y;
        Node(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
    public static Queue<Node> qSwan;
    public static Queue<Node> qLake;
    public static int[] dx = {-1, 1, 0, 0};
    public static int[] dy = {0, 0, -1, 1};

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

        // 행과 열의 크기
        r = Integer.parseInt(st.nextToken());
        c = Integer.parseInt(st.nextToken());

        // 호수 세팅, 백조 초기 위치 세팅
        lake = new char[r][c];
        visited = new boolean[r][c];
        qSwan = new LinkedList<Node>();
        int flag = 0;
        for(int i = 0; i < r; i++) {
            String[] strArr = br.readLine().split("");
            for(int j = 0; j < c; j++) {
                char ch = strArr[j].charAt(0);
                lake[i][j] = ch;
                // 백조 한마리를 G로 치환
                // L에서 시작해서 G를 찾는 탐색으로 진행하기 위함
                if(ch == 'L' && flag == 0) {
                    qSwan.offer(new Node(i, j));
                    visited[i][j] = true;
                    flag++;
                    sx = i;
                    sy = j;
                } else if(ch == 'L' && flag == 1) {
                    lake[i][j] = 'G';
                }
            }
        }

        // 빙판과 인접한 호수 칸 세팅
        melted = new boolean[r][c];
        qLake = new LinkedList<Node>();
        for(int i = 0; i < r; i++) {
            for(int j = 0; j < c; j++) {
                if(lake[i][j] == '.') {
                    for(int k = 0; k < 4; k++) {
                        int nx = i + dx[k];
                        int ny = j + dy[k];

                        if(isNearIce(nx, ny) && !melted[i][j]) {
                            qLake.offer(new Node(i, j));
                            melted[i][j] = true;
                        }
                    }
                }
            }
        }

        bw.write(String.valueOf(passDay()));
        bw.flush();
        bw.close();
        br.close();
    }

    public static boolean isNearIce(int x, int y) {
        if(x < 0 || x >= r || y < 0 || y >= c) {
            return false;
        } else {
            if (lake[x][y] == 'X') {
                return true;
            }
        }
        return false;
    }

    public static int passDay() {
        int day = 0;

        // 빙판 녹이기
        while(!qLake.isEmpty()) {

            // 백조가 다른 백조를 만날 수 있는지 확인 (최초 확인을 해야하므로 빙판을 녹이지 않고 찾아야함)
            while(!qSwan.isEmpty()) {
                Node cur = qSwan.poll();

                if(lake[cur.x][cur.y] == 'G') return day;

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

                    // 호수 범위를 벗어나거나, 이미 방문하였거나, 빙판으로 막혀있는 경우 skip
                    if(isNotRange(nx, ny) || visited[nx][ny] || lake[nx][ny] == 'X') continue;

                    qSwan.offer(new Node(nx, ny));
                    visited[nx][ny] = true;
                }
            }

            // 못찾았으면 다음날 다시 탐색을 위해서 큐와 방문배열 초기화
            qSwan.offer(new Node(sx, sy));
            visited = new boolean[r][c];

            // 큐에 담겨있는 사이즈 만큼만 녹여야 하루치임
            int size = qLake.size();

            for(int t = 0; t < size; t++) {
                Node cur = qLake.poll();

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

                    // 호수 범위를 벗어나거나, 이미 녹아있거나, 빙판이 아닌 경우 skip
                    if(isNotRange(nx, ny) || melted[nx][ny] || lake[nx][ny] != 'X') continue;

                    qLake.offer(new Node(nx, ny));
                    melted[nx][ny] = true;
                    lake[nx][ny] = '.';
                }
            }
            
            // 하루 경과
            day++;
        }

        return day;
    }

    public static boolean isNotRange(int x, int y) {
        return (x < 0 || x >= r || y < 0 || y >= c) ? true : false;
    }
}

2 시간초과

import java.io.*;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
    public static int r, c, sx, sy, day;
    public static char[][] lake;
    public static boolean[][] visited;
    public static boolean[][] melted;
    public static class Node {
        int x, y;
        Node(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
    public static Queue<Node> qSwan;
    public static Queue<Node> qLake;
    public static int[] dx = {-1, 1, 0, 0};
    public static int[] dy = {0, 0, -1, 1};

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

        // 행과 열의 크기
        r = Integer.parseInt(st.nextToken());
        c = Integer.parseInt(st.nextToken());

        // 호수 세팅, 백조 초기 위치 세팅
        lake = new char[r][c];
        int flag = 0;
        for(int i = 0; i < r; i++) {
            String[] strArr = br.readLine().split("");
            for(int j = 0; j < c; j++) {
                char ch = strArr[j].charAt(0);
                lake[i][j] = ch;
                // 백조 한마리를 G로 치환
                // L에서 시작해서 G를 찾는 탐색으로 진행하기 위함
                if(ch == 'L' && flag == 0) {
                    flag++;
                    sx = i;
                    sy = j;
                } else if(ch == 'L' && flag == 1) {
                    lake[i][j] = 'G';
                }
            }
        }

        // 빙판과 인접한 호수 칸 세팅
        melted = new boolean[r][c];
        qLake = new LinkedList<Node>();
        for(int i = 0; i < r; i++) {
            for(int j = 0; j < c; j++) {
                if(lake[i][j] == '.') {
                    for(int k = 0; k < 4; k++) {
                        int nx = i + dx[k];
                        int ny = j + dy[k];

                        if(isNearIce(nx, ny) && !melted[i][j]) {
                            qLake.offer(new Node(i, j));
                            melted[i][j] = true;
                        }
                    }
                }
            }
        }

        // 경과일수 count
        day = 0;

        // 백조들이 만날때까지 빙판 녹이기
        while(passDay());

        bw.write(String.valueOf(day));
        bw.flush();
        bw.close();
        br.close();
    }

    public static boolean isNearIce(int x, int y) {
        if(x < 0 || x >= r || y < 0 || y >= c) {
            return false;
        } else {
            if (lake[x][y] == 'X') {
                return true;
            }
        }
        return false;
    }

    public static boolean passDay() {
        qSwan = new LinkedList<Node>();
        visited = new boolean[r][c];
        qSwan.offer(new Node(sx, sy));
        visited[sx][sy] = true;

        // 백조가 다른 백조를 만날 수 있는지 확인 (최초 확인을 해야하므로 빙판을 녹이지 않고 찾아야함)
        while(!qSwan.isEmpty()) {
            Node cur = qSwan.poll();

            if(lake[cur.x][cur.y] == 'G') return false;

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

                // 호수 범위를 벗어나거나, 이미 방문하였거나, 빙판으로 막혀있는 경우 skip
                if(isNotRange(nx, ny) || visited[nx][ny] || lake[nx][ny] == 'X') continue;

                qSwan.offer(new Node(nx, ny));
                visited[nx][ny] = true;
            }
        }

        // 빙판 녹이기
        // 큐에 담겨있는 사이즈 만큼만 녹여야 하루치임
        int size = qLake.size();

        for(int t = 0; t < size; t++) {
             Node cur = qLake.poll();

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

                // 호수 범위를 벗어나거나, 이미 녹아있거나, 빙판이 아닌 경우 skip
                if(isNotRange(nx, ny) || melted[nx][ny] || lake[nx][ny] != 'X') continue;

                qLake.offer(new Node(nx, ny));
                melted[nx][ny] = true;
                lake[nx][ny] = '.';
            }

        }
        
        // 하루 경과
        day++;

        return true;
    }

    public static boolean isNotRange(int x, int y) {
        return (x < 0 || x >= r || y < 0 || y >= c) ? true : false;
    }
}

3 메모리 초과

import java.io.*;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
    public static int r, c, day;
    public static char[][] lake;
    public static boolean[][] visited;
    public static class Node {
        int x, y;
        Node(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
    public static Queue<Node> qSwan;
    public static Queue<Node> qLake;
    public static int[] dx = {-1, 1, 0, 0};
    public static int[] dy = {0, 0, -1, 1};

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

        // 행과 열의 크기
        r = Integer.parseInt(st.nextToken());
        c = Integer.parseInt(st.nextToken());

        // 호수 세팅, 백조 초기 위치 세팅
        lake = new char[r][c];
        qSwan = new LinkedList<Node>();
        visited = new boolean[r][c];
        int flag = 0;
        for(int i = 0; i < r; i++) {
            String[] strArr = br.readLine().split("");
            for(int j = 0; j < c; j++) {
                char ch = strArr[j].charAt(0);
                lake[i][j] = ch;
                // 백조 한마리를 G로 치환
                // L에서 시작해서 G를 찾는 탐색으로 진행하기 위함
                if(ch == 'L' && flag == 0) {
                    qSwan.offer(new Node(i, j));
                    visited[i][j] = true;
                    flag++;
                } else if(ch == 'L' && flag == 1) {
                    lake[i][j] = 'G';
                }
            }
        }

        // 빙판과 인접한 호수 칸 세팅
        qLake = new LinkedList<Node>();
        for(int i = 0; i < r; i++) {
            for(int j = 0; j < c; j++) {
                if(lake[i][j] == '.') {
                    for(int k = 0; k < 4; k++) {
                        int nx = i + dx[k];
                        int ny = j + dy[k];

                        if(isNearIce(nx, ny)) {
                            qLake.offer(new Node(i, j));
                        }
                    }
                }
            }
        }

        // 경과일수 count
        day = 0;

        // 백조들이 만날때까지 빙판 녹이기
        while(passDay());

        bw.write(String.valueOf(day));
        bw.flush();
        bw.close();
        br.close();
    }

    public static boolean isNearIce(int x, int y) {
        if(x < 0 || x >= r || y < 0 || y >= c) {
            return false;
        } else {
            if (lake[x][y] == 'X') {
                return true;
            }
        }
        return false;
    }

    public static boolean passDay() {
        // 다음날은 백조가 빙판에 가로막힌 지점부터 탐색하도록함
        Queue<Node> qNext = new LinkedList<Node>();

        // 백조가 다른 백조를 만날 수 있는지 확인 (최초 확인을 해야하므로 빙판을 녹이지 않고 찾아야함)
        while(!qSwan.isEmpty()) {
            Node cur = qSwan.poll();

            // 백조가 만났으면 return false
            if(lake[cur.x][cur.y] == 'G') return false;

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

                // 호수 범위를 벗어나거나, 이미 방문하였으면 skip
                if(isNotRange(nx, ny) || visited[nx][ny]) continue;

                // 빙판으로 막혀있는 경우 다음 큐에 담고 skip
                if(lake[nx][ny] == 'X') {
                    qNext.offer(new Node(nx, ny));
                    continue;
                }

                qSwan.offer(new Node(nx, ny));
                visited[nx][ny] = true;
            }
        }

        // 다음날 탐색 지점 세팅
        qSwan = qNext;

        // 빙판 녹이기
        // 큐에 담겨있는 사이즈 만큼만 녹여야 하루치임
        int size = qLake.size();

        for(int t = 0; t < size; t++) {
             Node cur = qLake.poll();

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

                // 호수 범위를 벗어나거나, 빙판이 아닌 경우 skip
                if(isNotRange(nx, ny) || lake[nx][ny] != 'X') continue;

                qLake.offer(new Node(nx, ny));
                lake[nx][ny] = '.';
            }
        }
        
        // 하루 경과
        day++;

        // 백조들이 못만났으므로 다시 수행
        return true;
    }

    public static boolean isNotRange(int x, int y) {
        return (x < 0 || x >= r || y < 0 || y >= c) ? true : false;
    }
}

4

import java.io.*;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
    public static int r, c, day;
    public static char[][] lake;
    public static boolean[][] visited;
    public static Node[] swan;
    public static class Node {
        int x, y;
        Node(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
    public static Queue<Node> qSwan;
    public static Queue<Node> qLake;
    public static int[] dx = {-1, 1, 0, 0};
    public static int[] dy = {0, 0, -1, 1};

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

        // 행과 열의 크기
        r = Integer.parseInt(st.nextToken());
        c = Integer.parseInt(st.nextToken());

        // 호수, 빙판 세팅
        lake = new char[r][c];
        qSwan = new LinkedList<Node>();
        qLake = new LinkedList<Node>();
        visited = new boolean[r][c];
        swan = new Node[2];

        int idx = 0;
        for(int i = 0; i < r; i++) {
            String[] strArr = br.readLine().split("");
            for(int j = 0; j < c; j++) {
                char ch = strArr[j].charAt(0);
                lake[i][j] = ch;

                if(ch == 'L') {
                    swan[idx++] = new Node(i, j);
                }
                if(ch != 'X') {
                    qLake.offer(new Node(i, j));
                }
            }
        }

        // 경과일수 count
        day = 0;

        // 초기 출발 백조 세팅
        qSwan.offer(swan[0]);
        visited[swan[0].x][swan[0].y] = true;

        // 백조들이 만날때까지 빙판 녹이기
        while(passDay());

        bw.write(String.valueOf(day));
        bw.flush();
        bw.close();
        br.close();
    }

    public static boolean passDay() {
        // 다음날은 백조가 빙판에 가로막힌 지점부터 탐색하도록하기 위함
        Queue<Node> qNext = new LinkedList<Node>();

        // 백조가 다른 백조를 만날 수 있는지 확인 (최초 확인을 해야하므로 빙판을 녹이지 않고 찾아야함)
        while(!qSwan.isEmpty()) {
            Node cur = qSwan.poll();

            // 백조가 만났으면 return false
            if(cur.x == swan[1].x && cur.y == swan[1].y) return false;

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

                // 호수 범위를 벗어나거나, 이미 방문하였으면 skip
                if(isNotRange(nx, ny) || visited[nx][ny]) continue;

                // 빙판으로 막혀있는 경우 다음 큐에 담고 skip
                if(lake[nx][ny] == 'X') {
                    qNext.offer(new Node(nx, ny));
                    visited[nx][ny] = true;
                    continue;
                }

                qSwan.offer(new Node(nx, ny));
                visited[nx][ny] = true;
            }
        }

        // 다음날 탐색 지점 세팅
        qSwan = qNext;

        // 빙판 녹이기
        // 큐에 담겨있는 사이즈 만큼만 녹여야 하루치임
        int size = qLake.size();

        for(int t = 0; t < size; t++) {
             Node cur = qLake.poll();

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

                // 호수 범위를 벗어나거나, 빙판이 아닌 경우 skip
                if(isNotRange(nx, ny) || lake[nx][ny] != 'X') continue;

                qLake.offer(new Node(nx, ny));
                lake[nx][ny] = '.';
            }
        }

        // 하루 경과
        day++;

        // 백조들이 못만났으므로 다시 수행
        return true;
    }

    public static boolean isNotRange(int x, int y) {
        return (x < 0 || x >= r || y < 0 || y >= c) ? true : false;
    }
}

Feedback

처음에 시간초과가 났다. 빙판은 녹이는 행위 안에 백조가 이동하도록 하는 구현을 하여 그런것인것 같아, 백조의 이동과 빙판 녹이기를 각각 구현하였다. 대신 전체를 while문에 넣고 백조끼리 만날때까지 돌도록 하였다.그래도 여전히 시간초과가 발생했다..

매번 하루가 지날때마다 백조가 처음 위치에서부터 다른 백조를 찾으러 가도록 하지 않고, 전날 빙판에 의해 막힌 지점부터 탐색을 이어나가도록 하여 해결하려고 solution 3과 같이 수정하였다.

그런데 이번엔 메모리 초과의 문제가 발생하였다..

빙판과 인접한 호수를 세팅하는 부분을 제거하고, 그냥 빙판이 아닌 칸은 전부 lake 큐에 담아버렸다. 그리고 백조 두 마리에 대해 출발하는 백조의 세팅을 배열하나를 만들어 관리하는 식으로 변경하였다. (구글링)