백준 : 3197

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

3197번: 백조의 호수

단순 BFS탐색으로는 많은 시간이 걸린다. 줄일수 있는건 2가지가 있다.

얼음이 녹는 시간을 사전에 미리구한다. 

현재위치가 X일때 상하좌우중 '.' 이 있다면 그칸은 1초에 녹는 칸이다.

그렇다면 2초 3초에 녹는 칸은 어떻게 구하는가?? 

Queue를 이용해서 visit[]처리를 하면서 한사이클식 time을 추가해준다. 그러면 0초일때는 현재 물인부분
1초일때는 녹는부분 2초일때 녹는 부분으로 mapCnt에 저장할수가 있다.

이렇게해서 0초부터 mapCnt 의 맥스값 까지 탐색하면 시간초과가 난다.

이때는 이분탐색을 이용해서 left = 0 right= mapCnt의 max값을 이용해서 mid = (left+right)/2 의 중간값이 

L두개가 서로 만나는지 확인한다. 만난다면 더작은 값을 구해야하므로 right = mid-1;를 한다.

만나지못한다면 left = mid+1 을한다 만나지못햇다면 왼쪽구간은 가봣자 이미 못구하는것을 알기 때문이다.

package day0301;
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
 
import day0301.B3197.Pair;
 
 
public class B3197 {
    static int N,M;
    static char[][] map;
    static int[][] mapCnt;
    static int[] dy = {1,-1,0,0};
    static int[] dx = {0,0,-1,1};
    static class Pair{
        int y;
        int x;
        public Pair(int y, int x) {
            super();
            this.y = y;
            this.x = x;
        }
        
    }
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        map = new char[N][M];
        Pair[] Node = new Pair[2];
        int cnt = 0;
        for(int i=0;i<N;i++) {
            map[i] = br.readLine().toCharArray();
            for(int j=0;j<M;j++) {
                if(map[i][j]=='L') {
                    Node[cnt++] = new Pair(i,j);
                }
            }
        }
        boolean[][] meltVisit = new boolean[N][M];
        Queue<Pair> melt = new LinkedList<>();
        for(int i=0;i<N;i++) {
            for(int j=0;j<M;j++) {
                if(map[i][j]=='X') {
                    for(int d=0;d<4;d++) {
                        int ny = i +dy[d];
                        int nx = j +dx[d];
                        if(ny<0||nx<0||ny>=N||nx>=M)continue;
                        if(map[ny][nx]=='X')continue;
                        melt.add(new Pair(i,j));
                        meltVisit[i][j] = true;
                        break;
                    }
                }
            }
        }
        
        int time =0;
        mapCnt = new int[N][M];
        while(!melt.isEmpty()) {
            int size = melt.size();
            time++;
            for(int s=0;s<size;s++){
                Pair tmp = melt.poll();
                mapCnt[tmp.y][tmp.x] = time;
                
                for(int d=0;d<4;d++) {
                    int ny = tmp.y +dy[d];
                    int nx = tmp.x +dx[d];
                    if(ny<0||nx<0||ny>=N||nx>=M)continue;
                    if(map[ny][nx]!='X')continue;
                    if(meltVisit[ny][nx])continue;
                    melt.add(new Pair(ny,nx));
                    meltVisit[ny][nx]=true;
                }
            }
        }
        
        int left =0; int right=time;
        int Answer =-1;
        while(left<=right) {
            int mid = (left+right)/2;
            
            boolean isCheck = false;
            
            Queue<Pair> q = new LinkedList<>();
            boolean visit[][] = new boolean[N][M];
            visit[Node[0].y][Node[0].x] = true;
            q.add(Node[0]);
            
            while(!q.isEmpty()) {
                Pair tmp = q.poll();
                if(tmp.y == Node[1].y && tmp.x == Node[1].x) {
                    isCheck = true;
                    break;
                }
                
                for(int d=0;d<4;d++) {
                    int ny = tmp.y +dy[d];
                    int nx = tmp.x +dx[d];
                    if(ny<0||nx<0||ny>=N||nx>=M)continue;
                    if(visit[ny][nx])continue;
                    if(mapCnt[ny][nx]>mid)continue;
                    visit[ny][nx] = true;
                    q.add(new Pair(ny,nx));
                }
            
            }
            
            if(isCheck) {
                Answer = mid;
                right = mid-1;
            }else {
        
                left=mid+1;
            }
        }
        System.out.println(Answer);
        
    }
    
}