문제

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

호수는 행이 R개, 열이 C개인 직사각형 모양이다. 어떤 칸은 얼음으로 덮여있다.

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

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

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

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

입력

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

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

출력

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

Java

import java.io.*;
import java.util.*;
public class Main {
    static int R, C, day=0;
    static boolean[][] visited;
    static char[][] arr;
    static Queue<Node> waterQ, q;
    static int[] dx = { -1, 1, 0, 0 };
    static int[] dy = { 0, 0, 1, -1 };

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] s = br.readLine().split(" ");
        C = Integer.parseInt(s[0]);
        R = Integer.parseInt(s[1]);
        arr = new char[C][R];
        visited = new boolean[C][R];
        waterQ = new LinkedList<>();
        q = new LinkedList<>();
        ArrayList<Node> swan = new ArrayList<>();

        for (int i = 0; i < C; i++) {
            char[] c = br.readLine().toCharArray();
            for (int j = 0; j < R; j++) {
                arr[i][j] = c[j];
                if (c[j] == 'L') {
                    swan.add(new Node(i, j));
                }
                if(c[j] != 'X') {
                    waterQ.add(new Node(i, j));
                }
            }
        }

        q.add(swan.get(0)); // 처음 백조 출발점.
        while(true) {
            if (findSwan(swan.get(1))) {
                System.out.println(day);
                break;
            }
            breakIce();
            day++;
        }

    }
    public static void breakIce() {
        int size = waterQ.size();
        for (int k = 0; k < size; k++) {
            Node n = waterQ.poll();
            for (int i = 0; i < 4; i++) {
                int nx = n.x + dx[i];
                int ny = n.y + dy[i];
                if (nx < 0 || ny < 0 || nx >= C || ny >= R)
                    continue;
                if (arr[nx][ny] == 'X') {
                    arr[nx][ny] = '.';
                    waterQ.add(new Node(nx, ny));
                }
            }
        }

    }
    public static boolean findSwan(Node end) {
        Queue<Node> swanQ = new LinkedList<>();
        while(!q.isEmpty()) {
            Node n = q.poll();
            if (n.x == end.x && n.y == end.y) {
                return true;
            }
            for (int i = 0; i < 4; i++) {
                int nx = n.x + dx[i];
                int ny = n.y + dy[i];
                if (nx < 0 || ny < 0 || nx >= C || ny >= R || visited[nx][ny])
                    continue;
                visited[nx][ny] = true;
                if (arr[nx][ny] == 'X') {
                    swanQ.add(new Node(nx, ny));
                    continue; // 얼음 벽은 갱신용이기 때문에 굳이 큐(q)에 추가할 필요X.
                }
                q.add(new Node(nx, ny));
            }
        }
        q = swanQ; // 백조가 만난 얼음벽이 다음 날 출발지점.

        return false;
    }
}
class Node {
    int x, y;
    Node (int x, int y) {
        this.x = x;
        this.y = y;
    }
}

• 처음 구성한 로직
  1. breakIce()메소드에서 반복문을 돌려 얼음을 큐에 넣는다.
  2. 물가 근처라면 얼음을 녹인다.
  3. 입력받을때 저장한 백조위치로 탐색한다. 만나면 종료. 아니면 반복.
  4. 1~3번 반복.
• 문제점
  • 매 반복마다 하는 방문처리와 얼음 찾는 로직 때문에 메모리 초과, 시간초과 발생.
  • 백조를 같은 위치에서만 출발했기 때문에 굳이 탐색이 필요하지 않은 곳까지 다시 탐색.
  • 또 생각해보니 백조를 먼저 탐색해서 만나면 끝나는데 순서가 바뀐것을 직감.

해결방안

• 백조, 물, 탐색 큐로 나눠서 운영.
• 백조 큐는 갱신용이기 때문에 전역변수로 하지 않음.
• 얼음 녹이는 작업은 굳이 방문이 필요하지 않으므로 큐(waterQ) 사이즈만큼 처리.
• 백조는 만나면 끝나지만 아니라면 마지막으로 탐색된 얼음벽의 위치를 다음 날 백조 시작 위치로 갱신(q -> swanQ).