백준 3197. 백조의 호수 :: 돼지개발자

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

"이분탐색, 맵 재정의"

 문제는 이분 탐색을 통해서도 풀 수 있고, 우선순위 큐를 통해서도 풀 수 있다. 더 나아가.. union find ? 를 통해서도 풀 수 있다는데 잘 모르

겠다.  이번 풀이에서는 우선순위 큐를 사용해서 풀도록 한다. 

사실 더 좋은 풀이가... 있는 것 같긴 하다 ㅠ 메모리 소요와 시간 초과가 너무 크다. 몇일 고생하다가 푼 문제라... 어쨌든 풀리긴 풀려서 다행.

그럼 풀이를 하면 가장 먼저 맵을 재정의 해야 한다. char[][] map 이외에 int[][] 형 맵을 별도로 두어 각 빙판이 몇일 째에 사라지는지를 마킹

한다. 그렇게 한 후, 이분 탐색을 한다면 빙판을 다 녹여보아서 end 값을 구하고, 구해지는 각 mid 값을 가지고 빙판을 탐색한다.

우선순위 큐를 사용한다고 하면, 맵을 재정의 한 후에 start 백조에서 end 백조까지 그냥 BFS 돌리면 된다. 우선순위 기준은 내가 지나온 빙판

위 숫자의 최대값 기준이다. 어렵다 ㅠㅠ

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.StringTokenizer;
 
class Main {
 
    static int R,C;
    static char[][] map;
    static int[][] water;
    static boolean[][] visited;
    static PriorityQueue<Node> q = new PriorityQueue<>();
    static Queue<Node> tq = new LinkedList<>();
    static int sx,sy,ex,ey;
    static int idx;
    static int[] dx = {0,0,1,-1};
    static int[] dy = {1,-1,0,0};
    
    public static void main (String[] args) throws IOException {
    
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        R = Integer.parseInt(st.nextToken());
        C = Integer.parseInt(st.nextToken());
        
        map = new char[R][C];
        water = new int[R][C];
        
        int idx = 0;
        for (int i = 0; i < R; i++) {
            char[] temp = br.readLine().toCharArray();
            for (int j = 0; j < C; j++) {
                map[i][j] = temp[j];
                if(temp[j] == 'L') {
                    map[i][j] = '.';
                    if(idx ++ == 0) {
                        sx = i;
                        sy = j;
                    }
                    else {
                        ex = i;
                        ey = j;
                    }
                }
            }
        }
        mark();
        System.out.println(solve());
    }
    
    static int solve() {
        visited = new boolean[R][C];
        
        visited[sx][sy] = true;
        q.add(new Node(sx, sy, 0));
        
        while(!q.isEmpty()) {
            
            Node cur = q.poll();
            
            if(cur.x == ex && cur.y == ey ) {
                return cur.day;
            }
            
            for (int i = 0; i < 4; i++) {
                int nx = cur.x + dx[i];
                int ny = cur.y + dy[i];
                
                if(!isRange(nx, ny) || visited[nx][ny])
                    continue;
                visited[nx][ny] = true;
                q.add(new Node(nx, ny, Math.max(cur.day, water[nx][ny])));
            }
        }
        return 0;
    }
    
    static void mark() {
        visited = new boolean[R][C];
        int day = 0;
        
        for (int i = 0; i < R; i++) {
            for (int j = 0; j < C; j++) {
                if(map[i][j] == '.') {
                    visited[i][j] = true;
                    tq.add(new Node(i, j, 0));
                }
            }
        }
        
        while(!tq.isEmpty()) {
            
            int size = tq.size();
            
            for (int s = 0; s < size; s++) {
                Node cur = tq.poll();
                
                water[cur.x][cur.y] = day;
                
                for (int k = 0; k < 4; k++) {
                    int nx = cur.x + dx[k];
                    int ny = cur.y + dy[k];
                    
                    if(!isRange(nx, ny) || visited[nx][ny]) continue;
                    
                    visited[nx][ny] = true;
                    tq.add(new Node(nx, ny,0));
                }
            }
            day++;
        }
    }
    
    static boolean isRange(int x, int y) {
        if( x < 0 || x >= R || y < 0 || y >= C) return false;
        return true;
    }
}
 
class Node implements Comparable<Node> {
    int x;
    int y;
    int day;
    
    Node( int x, int y, int day) {
        this.x = x;
        this.y = y;
        this.day = day;
    }
 
    @Override
    public int compareTo(Node o) {
        return this.day - o.day;
    }
}