[Java] 백준 3197번 : 백조의 호수

- 문제설명

 

---

 

- 해결과정

• 첫 번째 시도
  1. 호수 배열을 모두 돌며 녹아야 하는 빙하를 찾고 녹이는 메소드 작성
  2. 백조의 초기 위치부터 매번 BFS를 돌며 서로 만날 수 있는지 확인하는 메소드 작성
  3. 메인문에서 백조가 서로 만날 수 있을 때 까지 1,2번을 반복

이 방법으로 정확한 정답은 얻을 수 있었다. 그러나 시간초과가 발생했다.

이유가 뭘까? 빙하를 녹이는 메소드와 BFS 메소드 모두, 매번 처음부터 모든 배열을 다 뒤지면서 원하는 결과를 찾아간다.

문제 설명에 배열의 크기는 최대 1,500X1,500인데 최악의 경우 매번 1,250,000개의 좌표를 모두 탐색해야 하는 것이다.

백조가 서로 만나기까지 100일이 걸린다고 쳐도 시간복잡도가 12억이 넘어버린다. 

그럼 어떻게 개선해야 할까?

1,2번 메소드 모두 정답을 얻기까지 배열 전체를 단 한번만 순회하도록 만들어야 한다.

두 번째 해결과정을 보자.

 

• 두 번째 시도(최종)
  1. 호수 배열을 돌며 빙하를 녹여줄때 마지막으로 녹인 지점을 기억하고, 다음날이 됐을 때는 해당 지점부터 녹일 빙하를 찾아간다.
  2. BFS도 마찬가지이다. 최초 다른 백조를 찾아 나가다가 빙하에 막혀서 더이상 나아가지 못한다면, 다음 BFS에서는 막혔던 지점부터 BFS를 이어나가면 된다.
  3. 메인문에서 백조가 서로 만날 수 있을 때 까지 1,2번을 반복

이렇게 만들면 빙하를 녹이는 메소드, BFS 메소드 모두 각각 배열 전체를 한 번씩만 순회하게 된다. 

따라서 시간 복잡도를 해결할 수 있다.

 

 

---

 

- 솔루션

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

public class Main {

    private static int H, W, count;
    private static char[][] lake;
    private static int swan1_X, swan1_Y, swan2_X, swan2_Y;
    private static int[] dx = {1, -1, 0, 0};
    private static int[] dy = {0, 0, 1, -1};
    private static boolean isMeet;
    private static boolean[][] visited;
    private static Queue<int[]> waterQ = new LinkedList<>();
    private static Queue<int[]> newStart = new LinkedList<>();

    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());

        H = Integer.parseInt(st.nextToken());
        W = Integer.parseInt(st.nextToken());


        initLakeAndSearchSwan(br);
        visited = new boolean[H][W];
        while (true) {
            if (isMeet) {
                break;
            }
            nextDay();
            bfs(swan1_Y, swan1_X);
            int size = newStart.size();
            while (size-- > 0) {
                int[] poll = newStart.poll();
                bfs(poll[0], poll[1]);
            }
        }

        bw.write(Integer.toString(count));
        bw.flush();
        bw.close();
    }

    private static void initLakeAndSearchSwan(BufferedReader br) throws IOException {
        lake = new char[H][W];
        boolean isFirst = true;
        for (int i = 0; i < H; i++) {
            String line = br.readLine();
            for (int j = 0; j < W; j++) {
                lake[i][j] = line.charAt(j);
                if (line.charAt(j) == 'L') {
                    if (isFirst) {
                        swan1_X = j;
                        swan1_Y = i;
                        isFirst = false;
                    } else {
                        swan2_X = j;
                        swan2_Y = i;
                    }
                }
                if (line.charAt(j) == '.' || line.charAt(j) == 'L') {
                    waterQ.add(new int[]{i, j});
                }
            }
        }
    }

    private static void nextDay() {
        int size = waterQ.size();
		while (size-- > 0) {
			int[] currentWaterPoint = waterQ.poll();

			for (int i = 0; i < 4; i++) {
                int nextY = currentWaterPoint[0] + dy[i];
                int nextX = currentWaterPoint[1] + dx[i];
                try {
                    if (lake[nextY][nextX] == 'X') {
                        lake[nextY][nextX] = '.';
                        waterQ.add(new int[]{nextY, nextX});
                    }
                } catch (ArrayIndexOutOfBoundsException e) {}
			}
		}
        count++;
    }

    private static void bfs(int currentY, int currentX) {
        Queue<int[]> q = new LinkedList<>();
        q.add(new int[]{currentY, currentX});
        visited[currentY][currentX] = true;

        while (!q.isEmpty()) {
            int[] poll = q.poll();
            for (int i = 0; i < 4; i++) {
                int nextX = poll[1] + dx[i];
                int nextY = poll[0] + dy[i];
                try {
                    if (lake[nextY][nextX] != 'X' && !visited[nextY][nextX]) {
                        visited[nextY][nextX] = true;
                        q.add(new int[]{nextY, nextX});
                    } else if (lake[nextY][nextX] == 'X') {
                        newStart.add(new int[]{poll[0], poll[1]});
                    }
                    if (nextX == swan2_X && nextY == swan2_Y) {
                        isMeet = true;
                    }
                } catch (ArrayIndexOutOfBoundsException e) {}
            }
        }
    }
}