[백준] 3197번 백조의 호수 (platinum 5

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

class Point{
    int xy;
    int v;
    public Point(int xy, int v){
        this.xy=xy;
        this.v=v;
    }
}

public class Main{
    static int[] numx={-1,1,0,0};
    static int[] numy={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());
        int n=Integer.valueOf(st.nextToken());
        int m=Integer.valueOf(st.nextToken());

        PriorityQueue<Point> que=new PriorityQueue<>(new Comparator<Point>(){
            public int compare(Point o1, Point o2){
                return o1.v-o2.v;
            }
        });
        Queue<Point> que2=new LinkedList<>();
        ArrayList<Point> bird=new ArrayList<>();
        int[][] time=new int[n+1][m+1];
        for(int i=1; i<=n; i++){
            String a=br.readLine();
            for(int j=1; j<=m; j++){
                char c=a.charAt(j-1);
                if(c=='X'){
                    time[i][j]=-1;
                }
                //새의 위치 저장.
                //여기서 중요한점. 새가 앉은 곳은 얼음이 아니었다......(메모리 초과이후 틀린 이유)
                else if(c=='L'){
                    bird.add(new Point(j*10000+i,0));
                    que2.offer(new Point(j*10000+i,0));
                }
                //물의 위치를 que2에 넣기.
                //그리고 que2에서 bfs를 진행하면서, 얼음들을 녹이면
                //결국 얼음들은 물에서 그 얼음까지 도달한 시간이 얼음이 그날 만큼 지나야 
                //녹는다는 의미이다.
                else{
                    que2.offer(new Point(j*10000+i,0));
                }
            }
        }

        //빙판 싹 녹이기.
        //빙판이 녹는데 걸린 시간을 저장한다.
        while(!que2.isEmpty()){
            Point temp=que2.poll();
            for(int i=0; i<4; i++){
                int tx=temp.xy/10000+numx[i];
                int ty=temp.xy%10000+numy[i];

                if(tx<1 || tx>m || ty<1 || ty>n || time[ty][tx]!=-1){
                    continue;
                }
                time[ty][tx]=temp.v+1;
                que2.offer(new Point(tx*10000+ty, temp.v+1));
            }
        }

        que.clear();
        boolean[][] visit=new boolean[n+1][m+1];
        visit[bird.get(0).xy%10000][bird.get(0).xy/10000]=true;
        que.offer(bird.get(0));
		
        //하나의 백조를 넣고, 다른 백조까지 도달할 때까지, bfs를 진행한다.
        //이때 위에서는 물에서부터 진행으로, 어떤 얼음에 도달한 물은 가장 빨리 도착한 것이다.
        //하지만, 여기선 map에 다양한 시간이 걸려서 녹은 얼음들이 존재하므로, 
        //그냥 bfs를 돌린다고 최선의 선택이 아니다. 따라서, pq를 통해서,
        //해당지점까지 적게 걸린 케이스를 우선으로 뽑아내서 bfs를 진행한다.
        while(!que.isEmpty()){
            Point temp=que.poll();
            int tempx=temp.xy/10000;
            int tempy=temp.xy%10000;
            if(tempx==bird.get(1).xy/10000 && tempy==bird.get(1).xy%10000){
                bw.write(temp.v+"");
                break;
            }
            for(int i=0; i<4; i++){
                int tx=tempx+numx[i];
                int ty=tempy+numy[i];

                if(tx<1 || tx>m || ty<1 || ty>n || visit[ty][tx]){
                    continue;
                }
                visit[ty][tx]=true;
                int day= temp.v > time[ty][tx] ? temp.v : time[ty][tx];
                que.offer(new Point(tx*10000+ty, day));
            }


        }
        bw.flush();
    }
}