[백준] 3197 백조의 호수 - JAVA

3197번: 백조의 호수 (acmicpc.net)

3197번: 백조의 호수

 

처참했던 흔적....

 

많이 해맸던 문제인데 풀이가 의외로 단순했다

 

풀이

알고리즘 파악

BFS

 

구현

 

1.백조를 움직이고 얼음을 만나면 멈추기 각 위치를 queue에 저장

2.얼음의 위치를 queue 에 담아두고 녹이기 + 다음에 녹일 얼음을 queue 저장

3.백조가 서로 만나면 종료

 

1) 얼음을 녹이는것 부터 살펴보자. 얼음을 녹일때 항상 1행 1열 부터 시작하면 엄청난 시간 낭비이다. 그래서 생각한것이 모든 얼음을 queue에 저장시키고 녹인뒤 다음턴에 녹을 얼음을 다시 저장시키는 것이었다. 큐 2개를 만들어 현재 얼음과 다음위치를 저장하였다. 이 아이디어는 처음부터 쉽게 생각하였으나 문제는 백조였다. 

 

2) 처음에는 얼음으로 둘러 쌓인 영역들을 전부 분리하였다. 그리고 얼음이 녹을때 마다 영역들을 합병하고 종국에는 두 백조의 영역을 확인하였다. 하지만 이는 결과적으로 시간초과를 낳았다. 분리된 영역이 적으면 상관없지만 너무 많아지니 일일히 영역의 합병을 확인하는것이 오래걸린 것이다. 

해답은 은근 단순하였는데 백조를 별도로 움직이고 그 위치를 전부 Queue에 저장하는것 이였다. 백조가 얼음을 만나면 움직을 종료하고 위치를 queue 저장하여 다음턴에 다시 움직인다.

 

 

 

 

import java.io.*;
import java.util.StringTokenizer;
import java.util.Queue;
import java.util.LinkedList;
public class Main {
	static int r,c,answer;
	static int des_x,des_y;
	static char[][] map;
	static boolean end=false;
	static int[] dx = {1,-1,0,0};
	static int[] dy = {0,0,1,-1};
	static boolean[][] swan_check,water_check;
	static Queue<int[]> swan = new LinkedList<>(); //대기 백조 목록
	static Queue<int[]> water= new LinkedList<>(); //대기 얼음 목록
    
    public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
    	 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];
         swan_check = new boolean[r][c];
         water_check = new boolean[r][c];
         for(int i=0; i<r; i++)
         {
        	 st = new StringTokenizer(br.readLine(),"");
        	 String[] arr = st.nextToken().split("");
        	 for(int j=0; j<c; j++) 
        	 {
        		 map[i][j] = arr[j].charAt(0);
        		 int[] loc = {i,j};
        		 if(arr[j].charAt(0) == '.' || arr[j].charAt(0) == 'L') water.offer(loc);
        		 if(arr[j].charAt(0) == 'L')
        		 {
        			 if(swan.isEmpty())swan.add(loc);
        			 else 
        			 {
        				 des_x = i;
        				 des_y = j;
        			 }
        		 }
        	 } 
         }
         while(!end)
         {
        	 Queue<int[]> swan_copy = copy(); //이동 백조큐 생성
        	 move_swan(swan_copy); //백조 이동
        	 if(end) break; //만남 -> 종료
        	 melt_ice();//얼음 녹이기
                 answer++; //시간 증가
         }
         System.out.println(answer);
	}
    static Queue<int[]> copy() // 대기 하던 백조 큐를 이동할 백조큐로 변환
    {
    	Queue<int[]> copy =  new LinkedList<>();
    	while(!swan.isEmpty())
    	{
    		copy.offer(swan.poll());
    	}
    	return copy;
    }
    static void move_swan(Queue<int[]> queue) //백조 움직이기
    {
    	Queue<int[]> temp = new LinkedList<>();
    	while(!queue.isEmpty())
    	{
    		int[] arr = queue.poll();
    		for(int i=0; i<4; i++)
    		{
    		  int x= arr[0] + dx[i];
    		  int y = arr[1] + dy[i];
    		  if(x>=0&&x<r&&y>=0&&y<c&&!swan_check[x][y])
    		  {
    			  swan_check[x][y] = true;
    			  if(map[x][y] == 'X') //얼음 -> 다음턴에 이동
    			  {
       			      int[] temp_a = {x,y};
    				  swan.offer(temp_a); //대기할 백조 목록
    			  }
    			  else 
    			  { 
    			   int[] temp_a = {x,y};
       			   temp.add(temp_a);
    			  }
    		  }
    		  if(x == des_x && y == des_y) {end = true; break;}
    		}
    		if(end) break;
    	}
    	if(!temp.isEmpty() && !end) move_swan(temp);
    }
     static void melt_ice() //얼음 녹이기
    {
    	Queue<int[]> temp = new LinkedList<>();
    	while(!water.isEmpty())
    	{
    		int[] arr = water.poll();
    		
    		for(int i=0; i<4; i++)
    		{
    		  int x= arr[0] + dx[i];
    		  int y = arr[1] + dy[i];
    		   if(check_ice(x,y)) //녹여
    		   {
    			   map[x][y] = '.';
    			   int[] temp_a = {x,y};
    			   temp.add(temp_a);
    		   }
    		}
    	}
    	water = temp;
    }
    static boolean check_ice(int x, int y) //다음 녹일 얼음 확인
    {
    	if(x<0||x==r||y<0||y==c||water_check[x][y]) return false;
    	water_check[x][y] = true;
    	if(map[x][y] == 'X') return true;
    	return false;
    }
}