백준 3197 : 백조의 호수 _Java

 

문제

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

3197번: 백조의 호수

 

#BFS #Platinum5

 

접근 방법

백조는 한마리만 이동 시켜도 된다.
(처음에는 두마리 다 이동 시켜야 하는 줄 알았다.. 그러나 그럴 필요가 없었던..ㅠ)

1. 입력 받을 때,
 1-1. 물을 water큐에 넣는다. 
 1-2. 백조 한마리는 swan큐에 넣고, 다른 한마리는 위치만 저장해준다.

2. 백조를 이동시킨다.
 2-1. 다른 백조를 만나면 종료시킨다.
 2-2. 얼음을 만나면 swanNext큐에 넣는다.

3. 얼음을 녹인다.
 3-1. 얼음을 만나면 waterNext큐에 넣는다.

4. 시간을 증가시킨다.

 

회고

위의 로직으로 구현하였는데, 약 6번정도의 메모리 초과가 발생했었다.

아무리 생각해도 생각한 로직이 맞는데 왜 틀렸는지 이해가 안됐었는데 .... 코드를 눈 빠져라 다시 본 결과

 

waterNext 큐에 다음 녹을 위치를 넣어줄 때, 다음 위치를 넣었어야 했는데 현재 위치를 넣는 멍청한 실수를 해서 중복되는 위치가 들어가서 메모리 초과가 났던 것 같다. 😓😓😓

 

아무튼 이 문제는 무려 그래프의 크기가 "1500 x 1500" 이어서 next 큐를 이용해서 다음에 얼음이 녹을 위치와 백조가 이동할 위치를 저장해줘야 하는 문제였다.

 

플래티넘 치고는 난이도가 쪼오오오끔 낮은 편이라고 생각하지만 처음으로 플래티넘을 풀어서 감격스럽다. 😎😎

 

코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayDeque;
import java.util.Queue;
import java.util.StringTokenizer;

public class 백조의호수_3197 {
    static final char ICE = 'X', SWAN = 'L', WATER = '.';
    static final int[][] deltas = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};

    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    static StringTokenizer st;

    static int R, C;
    static int ans = 0;
    static boolean isEnd = false;

    static char[][] graph;
    static boolean[][] visited;
    static Queue<Node> waterQ, waterNextQ;
    static Queue<Node> swanQ, swanNextQ;

    static Node swan;


    public static void main(String[] args) throws Exception {
        st = new StringTokenizer(br.readLine());
        R = Integer.parseInt(st.nextToken());
        C = Integer.parseInt(st.nextToken());

        graph = new char[R][C];
        visited = new boolean[R][C];

        waterQ = new ArrayDeque<>();
        waterNextQ = new ArrayDeque<>();
        swanQ = new ArrayDeque<>();
        swanNextQ = new ArrayDeque<>();

        for (int r = 0; r < R; r++) {
            String s = br.readLine();
            for (int c = 0; c < C; c++) {
                graph[r][c] = s.charAt(c);
                if (graph[r][c] != ICE) {
                    waterQ.offer(new Node(r, c));
                }
                if (graph[r][c] == SWAN) {
                    if (swanQ.isEmpty()) {
                        swanQ.offer(new Node(r, c));
                        visited[r][c] = true;
                    } else {
                        swan = new Node(r, c);
                    }
                }
            }
        }

        while (true) {
            // 백조 이동
            moveSwan();
            if (isEnd) break;

            // 얼음 녹기
            meltIce();
            ans++;
        }
        bw.write(ans + ""); bw.flush(); bw.close();
    }

    private static void moveSwan() {
        while (!swanQ.isEmpty()) {
            Node cur = swanQ.poll();

            if (cur.r == swan.r && cur.c == swan.c) {
                isEnd = true;
                return;
            }

            for (int dir = 0; dir < deltas.length; dir++) {
                int nr = cur.r + deltas[dir][1];
                int nc = cur.c + deltas[dir][0];

                if (!scope(nr, nc)) continue;
                if (visited[nr][nc]) continue;

                visited[nr][nc] = true;
                if (graph[nr][nc] == ICE) {
                    swanNextQ.offer(new Node(nr, nc));
                } else {
                    swanQ.offer(new Node(nr, nc));
                }
            }
        }

        while (!swanNextQ.isEmpty()) {
            swanQ.offer(swanNextQ.poll());
        }
    }

    private static void meltIce() {
        while (!waterQ.isEmpty()) {
            Node cur = waterQ.poll();

            for (int dir = 0; dir < deltas.length; dir++) {
                int nr = cur.r + deltas[dir][1];
                int nc = cur.c + deltas[dir][0];
                if (!scope(nr, nc)) continue;

                if (graph[nr][nc] == ICE) {
                    graph[nr][nc] = WATER;
                    waterNextQ.offer(new Node(nr, nc));
                }
            }
        }

        while (!waterNextQ.isEmpty()) {
            waterQ.offer(waterNextQ.poll());
        }
    }

    private static boolean scope(int r, int c) {
        return r >= 0 && r < R && c >= 0 && c < C;
    }
    
    static class Node {
        int r, c;

        public Node(int r, int c) {
            this.r = r;
            this.c = c;
        }
    }
}