[백준] 3197 백조의 호수 #JAVA #BFS #시간초과

[백준] 3197 백조의 호수 #JAVA #BFS #시간초과

---

코드

---

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

public class Main {
	
	static int[] dx = {0,1,0,-1};
	static int[] dy = {1,0,-1,0};
	static int R, C;
	static char[][] map;
	static boolean[][] visSwan, visWater;
	static Queue<int[]> waterQ, waterNextQ, swanQ, swanNextQ;
	
	static int startX, startY, endX, endY;
	
	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()); //y
		C = Integer.parseInt(st.nextToken()); //x
		
		map = new char[R][C];
		
		visSwan = new boolean[R][C];
		swanQ = new LinkedList<>();
		swanNextQ = new LinkedList<int[]>();
		
		visWater = new boolean[R][C];
		waterQ = new LinkedList<int[]>();
		waterNextQ = new LinkedList<int[]>();
		
		int resultDays = -1;
		
		List<int[]> startEnd = new ArrayList<int[]>();
		
		for (int i = 0; i < R; i++) {
			String temp = br.readLine();
			for (int j = 0; j < C; j++) {
				
				if(temp.charAt(j) == 'X') {
					map[i][j] = 'X';
					
				}else {
					if(temp.charAt(j) == 'L') {
						startEnd.add(new int[] {j,i}); //x,y
					}
					waterQ.add(new int[] {j,i}); //x,y
					visWater[i][j] = true;
					map[i][j]='.';
				}
				
			}
		}
		
		startX =  startEnd.get(0)[0];
		startY =  startEnd.get(0)[1];
		endX =  startEnd.get(1)[0];
		endY =  startEnd.get(1)[1];
		
		visSwan[startY][startX] = true;
		swanQ.add(new int[] {startX, startY});

		while (!visSwan[endY][endX]) {
			waterBFS();
			swanBFS();
			resultDays++;
		}
		
		System.out.println(resultDays);
		
	}
	
	private static void swanBFS() {
		
		while (!swanNextQ.isEmpty()) {
			swanQ.add(swanNextQ.poll());
		}
		
		
		while (!swanQ.isEmpty()) {

			int[] cur = swanQ.poll();

			int x = cur[0];
			int y = cur[1];

			for (int k = 0; k < 4; k++) {
				int nx = x + dx[k];
				int ny = y + dy[k];

				if (nx < 0 || ny < 0 || nx >= C || ny >= R)	continue;
				if (visSwan[ny][nx]) continue;

				if (map[ny][nx] == 'X') {
					swanNextQ.add(new int[] {nx, ny});
				} else {
					swanQ.add(new int[] {nx, ny});
				}
				
				visSwan[ny][nx] = true;
			}
		}
	}
	
	private static void waterBFS() {
		while (!waterNextQ.isEmpty()) {
			int[] cur = waterNextQ.poll();
			map[cur[1]][cur[0]] = '.';
			waterQ.add(cur);
		}
		
		while (!waterQ.isEmpty()) {

			int[] cur = waterQ.poll();

			int x = cur[0];
			int y = cur[1];
			
			for (int k = 0; k < 4; k++) {
				int nx = x + dx[k];
				int ny = y + dy[k];

				if (nx < 0 || ny < 0 || nx >= C || ny >= R)	continue;
				if (visWater[ny][nx]) continue;
				
				if (map[ny][nx] == 'X') {
					waterNextQ.add(new int[] {nx, ny});
					visWater[ny][nx] = true;
				}
				
			}
		}
	}
}

 

 

풀이

---

1. BFS를 통해 빙하를 녹여 물로 만든다.
   • 시간 단축을 위해 2개의 큐를 사용한다. waterQ, waterNextQ(다음 턴에 물이 될 좌표)
   • waterQ를 BFS하며 다음 턴에 빙하에서 물이 될 좌표를 탐색하여 waterNextQ에 담는다.
   • 턴이 지날 때 마다 waterNextQ의 좌표를 waterQ로 옮긴다. 이 때, map을 'X(빙하)'에서 '.(물)'로 변환한다.
2. BFS를 통해 백조가 만날 수 있는지 확인한다.
   • 시간 단축을 위해 2개의 큐를 사용한다. swanQ, swanNextQ(다음 턴에 백조가 갈 수 있는 좌표)
   • swanQ를 BFS하며 다음 턴에 백조가 갈 수 있는 좌표를 탐색하여 swanNextQ에 담는다.
3. 다른 백조가 있는 좌표에 방문 가능 할 때까지 1번과 2번을 반복한다.

 

주의 사항

---

• 백조의 좌표는 물이다. 물에 대한 BFS를 돌릴 때 해당 좌표를 큐에 넣어야 한다.

 

 

---

잘못된 코드나 내용이 있다면 댓글을 남겨주세요. 즉시 수정하도록 하겠습니다! :)