백준 3197 : 백조의 호수 (JAVA) 2번째풀이

2번째로 풀었을 때에는 메모리 초과가 이슈였다.
메모리 초과의 핵심원인은 "얼음을 녹이는 과정에서 큐에 모든 물을 담았기 때문이었다."
따라서 해결 방법은 큐에 물의 좌표를 담는 것이 아닌 "녹은 물"만 담는 것이었다.

java 코드

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

public class Main {
    static int dx[] = {0,1,0,-1};
    static int dy[] = {-1,0,1,0};
    static int r,c,day;
    static char[][] mp;
    static boolean[][] baek_vis;
    static Queue<Point> water_q , baek_q , water_temp_q,baek_temp_q,temp_q;
    static Point l1;
    public static void main(String[] args) throws IOException {
        // 1. input
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        r = Integer.parseInt(st.nextToken());
        c = Integer.parseInt(st.nextToken());
        baek_vis = new boolean[r][c];
        mp = new char[r][c];
        water_q = new LinkedList<>();
        baek_q = new LinkedList<>();
        water_temp_q = new LinkedList<>();
        baek_temp_q = new LinkedList<>();
        temp_q = new LinkedList<>();
        String str;
        l1 = new Point(0,0);
        for(int i=0;i<r;i++){
            str = br.readLine();
            for(int j=0;j<c;j++){
                mp[i][j]=str.charAt(j);
                if(mp[i][j]=='L'){l1.x = j; l1.y =i;}
                if(mp[i][j]=='.' || mp[i][j]=='L'){
                    water_q.add(new Point(j,i));
                }
            }
        }
        baek_q.add(new Point(l1.x,l1.y));
        baek_vis[l1.y][l1.x]=true;
        // 2. bfs
        while(!find()){
            melting();
            day++;
        }

        System.out.println(day);
    }

    static boolean find(){
        boolean res = false;
        int cx,cy,nx,ny;
        Point cp;
        while(!baek_q.isEmpty()){
            cp = baek_q.poll();
            cx = cp.x; cy = cp.y;
            for(int i=0;i<4;i++){
                nx = cx+dx[i];
                ny = cy+dy[i];
                if(nx<0||nx>=c||ny<0||ny>=r||baek_vis[ny][nx]) continue;
                baek_vis[ny][nx] = true;
                if(mp[ny][nx]=='X') {
                    baek_temp_q.add(new Point(nx,ny));
                }
                else if(mp[ny][nx]=='.'){
                    baek_q.add(new Point(nx,ny));
                }
                else if(mp[ny][nx]=='L'){
                    res = true;
                    break;
                }
            }
            if(res) break;
        }
        temp_q = baek_q;
        baek_q = baek_temp_q;
        baek_temp_q = temp_q;

        return res;
    }
    static void melting(){
        int cx,cy,nx,ny;
        Point cp;
        while(!water_q.isEmpty()){
            cp = water_q.poll();
            cx = cp.x; cy = cp.y;
            for(int i=0;i<4;i++){
                nx = cx + dx[i];
                ny = cy + dy[i];
                if(nx<0||nx>=c||ny<0||ny>=r) continue;
                if(mp[ny][nx]=='.') continue; // 이미 물인 것은 큐에 담지 않는다.
                if(mp[ny][nx]=='X'){
                    water_temp_q.add(new Point(nx,ny)); // 녹는 얼음만 담는다.
                    mp[ny][nx]='.';
                }
            }
        }
        temp_q=water_q;
        water_q=water_temp_q;
        water_temp_q=temp_q;

    }

}
class Point {
    int x,y;
    Point(int x, int y){
        this.x =x; this.y =y;
    }
}