(JAVA) 백준 3197번 : 백조의 호수

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

 

 

 

 

 

 

이전에 실패했던 문제를 다시 보고 있다.

이 문제는 BFS를 이용한 문제로 1년전 다시 풀지 못했던 문제다.

 

다음 코드는 메모리 초과로 틀린 코드이다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
import java.util.Queue;
import java.util.LinkedList;
 
public class B_3197 {
    static int R,C,ti=0,A,B;
    static int[][] dic= {{0,1},{1,0},{-1,0},{0,-1}};
    static Queue<int[]> que1,que2;
    static int[][] visited;
    static boolean[][] ch;
    static boolean check(int x,int y) {
        if (x<0||x>=R) return false;
        else if (y<0||y>=C) return false;
        return true;
    }
    static boolean fedge() {//백조주변의 물을 체크(체크시 백조가 나오면 true를 반환)
        int n =que2.size();
        for(int t=0;t<n;t++) {
            Queue<int[]> qque = new LinkedList<>();
            int[] k = que2.poll();
            qque.add(k);
            while(qque.isEmpty()!=true) {
                int[] a = qque.poll();
                int pp=visited[a[0]][a[1]];
                for (int i=0;i<4;i++) {
                    int aa=a[0]+dic[i][0],bb=a[1]+dic[i][1];
                    if (check(aa,bb)==false)continue;
                    if (visited[aa][bb]==pp)continue;
                    if (visited[aa][bb]*pp==2) {
                        A=aa; B=bb;
                        return true;
                    }
                    if(visited[aa][bb]==-1) {
                        
                        visited[aa][bb]=pp;
                        int[] w = {aa,bb};
                        qque.add(w);
                    }
                    else if(visited[aa][bb]==-3){
                        int[] w = {aa,bb};
                        que2.add(w);
                        visited[aa][bb]=pp;
                    }
                    
                }
            }
        }
        return false;
    }
    static boolean ffedge() {
        int n=que1.size();
        for (int t=0;t<n;t++) {
            Queue<int[]> qque = new LinkedList<>();
            int[] k = que1.poll();
            if (visited[k[0]][k[1]]>0) continue;
            qque.add(k);
            while(qque.isEmpty()!=true) {
                int[] a = qque.poll();
                ch[a[0]][a[1]]=true;
                visited[a[0]][a[1]]=-1;
                for (int i=0;i<4;i++) {
                    int aa=a[0]+dic[i][0],bb=a[1]+dic[i][1];
                    if (check(aa,bb)==false)continue;
                    if (ch[aa][bb]==true)continue;
                    if(visited[aa][bb]==-3) {
                        int[] w = {aa,bb};
                        que1.add(w);
                    }
                    else if (visited[aa][bb]==-1) {
                        int[] w = {aa,bb};
                        qque.add(w);
                    }
                }
            }
        }
        return false;
    }
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        R = Integer.parseInt(st.nextToken());
        C = Integer.parseInt(st.nextToken());
        que1 = new LinkedList<>();que2 = new LinkedList<>();
        visited = new int[R][C];
        ch= new boolean[R][C];
        int p=1;
        for (int i=0;i<R;i++) {
            String s =br.readLine();
            for (int j=0;j<C;j++) {
                char a = s.charAt(j);
                int[] w = {i,j};
                if (a=='.') {
                    visited[i][j]=-1;
                    que1.add(w);
                }
                else if (a=='X') {
                    visited[i][j]=-3;
                }
                else if (a=='L') {
                    que2.add(w);
                    visited[i][j]=p;
                    p+=1;
                }
            }
        }
        
        while(true) {
            if (fedge()==true) {
                if (visited[A][B]==1) ti+=1;
                break;
            }
            ffedge();
            ti+=1;
        }
        System.out.println(ti);
        }
 
}
 

 

- 매일 물과 접촉한 가로세로의 얼음이 녹는다.

- 백조는 물공간에서 세로나 가로로 움직일 수 있다.

- 며칠이 지나야 백조를 만날수 있는지를 구한다.

 

- BFS를 이용해 다른 백조를 만날 수 있는지 탐색한다.

- 근처 얼음을 녹이는 물의 위치를 따로 waterQueue 에 담는다.

- 다른 백조의 탐색은 swanQueue에서 진행한다. (하나의 백조에서 다른 백조까지 가기 위해)

- visited는 1이 시작하는 백조의 방문처리이고, 2가 나머지 하나의 백조(만나야 하는 백조)이며, -1은 물, -3은 얼음을 나타냈다.

- meetSwan() 에서는 백조에 대한 BFS로 현재 다른 백조에 도달할 수 있는지를 확인하며, 백조의 근처 얼음의 경우 얼음이 녹은 다음날에는 탐색이 가능하기에 이들을 전부 nextSwanQueue에 넣어두고 SwanQueue를 업데이트한다.

- meltIce() 에서는 저장된 물 근처의 얼음들을 녹이는데 녹은 얼음들의 위치를 nextWaterQueue에 넣어 WaterQueue를 업데이트 한다.

 

- 아래는 성공한 코드이다. (메모리도 시간도 부족했기에 다른 분들의 풀이를 참고하고 보완해야한다.)

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
import java.util.Queue;
import java.util.LinkedList;
 
class XY {
    int x, y;
    public XY(int x, int y) {
        this.x = x;
        this.y = y;
    }
}
 
public class B_3197 {
    static int R, C;
    static int[][] dic = { { 0, 1 }, { 1, 0 }, { -1, 0 }, { 0, -1 } };
    static Queue<XY> swanQueue, waterQueue;
    static int[][] visited;
    static boolean[][] waterVisited;
 
    static boolean check(int x, int y) {
        return x >= 0 && x < R && y >= 0 && y < C;
    }
 
    static boolean meetSwan() {
        Queue<XY> nextSwanQueue = new LinkedList<>();
        
        while (!swanQueue.isEmpty()) {
            XY current = swanQueue.poll();
            for (int i = 0; i < 4; i++) {
                int nx = current.x + dic[i][0];
                int ny = current.y + dic[i][1];
                if (!check(nx, ny)) continue;
                if (visited[nx][ny] == 1) continue;  // 이미 탐색한 영역
                if (visited[nx][ny] == 2) return true;  // 다른 백조와 만남
                
                if (visited[nx][ny] == -3) {  // 얼음인 경우
                    nextSwanQueue.add(new XY(nx, ny));
                } else {
                    swanQueue.add(new XY(nx, ny));  // 물 영역
                }
                visited[nx][ny] = 1;  // 방문 처리
            }
        }
        
        swanQueue = nextSwanQueue;  // 얼음이 녹아 다음 탐색 대상이 되는 영역을 업데이트
        return false;
    }
 
    static void meltIce() {
        Queue<XY> nextWaterQueue = new LinkedList<>();
        
        while (!waterQueue.isEmpty()) {
            XY current = waterQueue.poll();
            for (int i = 0; i < 4; i++) {
                int nx = current.x + dic[i][0];
                int ny = current.y + dic[i][1];
                if (!check(nx, ny)) continue;
                if (waterVisited[nx][ny]) continue;  // 이미 녹은 물
                
                if (visited[nx][ny] == -3) {  // 얼음인 경우
                    visited[nx][ny] = -1;  // 물로 변경
                    nextWaterQueue.add(new XY(nx, ny));  // 다음 녹일 얼음
                }
            }
        }
        
        waterQueue = nextWaterQueue;  // 다음에 녹일 얼음들을 저장
    }
 
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        R = Integer.parseInt(st.nextToken());
        C = Integer.parseInt(st.nextToken());
        
        swanQueue = new LinkedList<>();
        waterQueue = new LinkedList<>();
        visited = new int[R][C];
        waterVisited = new boolean[R][C];
        
        XY swan1 = null, swan2 = null;
        
        for (int i = 0; i < R; i++) {
            String line = br.readLine();
            for (int j = 0; j < C; j++) {
                char c = line.charAt(j);
                if (c == '.') {
                    visited[i][j] = -1;  // 물
                    waterQueue.add(new XY(i, j));
                    waterVisited[i][j] = true;
                } else if (c == 'X') {
                    visited[i][j] = -3;  // 얼음
                } else if (c == 'L') {
                    visited[i][j] = -1;  // 백조가 있는 물
                    waterQueue.add(new XY(i, j));
                    waterVisited[i][j] = true;
                    if (swan1 == null) {
                        swan1 = new XY(i, j);
                        swanQueue.add(swan1);
                        visited[i][j] = 1;
                    } else {
                        swan2 = new XY(i, j);
                        visited[i][j] = 2;
                    }
                }
            }
        }
 
        int days = 0;
        while (true) {
            if (meetSwan()) { 
                System.out.println(days);
                break;
            }
            meltIce();
            days++;
        }
    }
}