[백준/BFS] 3055: 탈출 - 자바

문제

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

3055번: 탈출

풀이

문제에서 주어진 조건을 확인하자.

R X C 행열로 주어지고 비어있는 곳은 ' . ' , 물이 차 있는 지역은 ' * ' , 돌은 ' X  ' 로 표시되어 있다. 

비버의 굴은 'D' 고슴도치 위치는 'S' 로 나타내어져 있다. 

 

문제에서 원하는 것은 고슴도치 'S'가 비버의 굴 'D'까지 이동할 수 있다면 걸린 최소 시간을 구하는 것이 목적이다.

문제에서는 고슴도치는 물에 바쪄 죽지 않기 위해 물이 차 오르는 곳으로 이동할 수 없다. 

그래서 한 타임동안 물을 확장 -> 고슴도치 이동을 해야한다.

 

먼저 물의 좌표를 큐에 넣고 사방탐색하여 물의 범위를 확장시켰다.

이후 고슴도치를 BFS 탐색을 하였다.

 

맨 처음 풀었을 때 물의 범위를 확장하고 고슴도치의 최단경로를 BFS를 하였는데 고슴도치가가 한 방향으로 탐색할 때 마다 물이 한칸씩 확장하여서 물의 좌표를 탐색하는 큐와 고슴도치의 최단 경로를 탐색하는 큐를 분리하였다

 

그리고 큐 사이즈는 물의 좌표 수만큼 4방 탐색하고 고슴도치가 한 좌표에서 4방 탐색하고 다시 물의탐색을 진행하기 위해사이즈를 사용하였다.

 

맨 처음에 메모리 초과가 발생하였는데 while문 안에 배열을 계속 생성하였기 때문이다.

copymap은 물을 퍼트리고 바로 맵에 적용시키면 이중 for문을 돌면서 이전에 바로 물이 퍼진곳에서 다시 물을 퍼트리기 때문에(?) 바로 적용시키지 않기 위해 사용하였다.

 

하지만 다음 탐색할 곳을 큐에 넣고 퍼진 곳을 맵에 적용하면 따로 copyMap을 쓰지 않아도 된다.

아래는 본인이 작성한 코드이다. 

 

풀이1

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Queue;
import java.util.StringTokenizer;

public class BOJ_3055 {
	static StringTokenizer st;
	static int R, C, waterX, waterY, biberX, biberY;
	static char[][] map;
	static int[] dx = {-1,1,0,0};
	static int[] dy = {0,0,-1,1};
	static Queue<int[]> waterQueue = new ArrayDeque<>();
	static Queue<int[]> moveQueue = new ArrayDeque<>();
	
	public static void main(String[] args) throws IOException {
		input();
		int[][] visited = new int[R][C];
		BFS(visited);
		System.out.println("KAKTUS");
	}

	public static void BFS(int[][] visited) {
		
		while(!waterQueue.isEmpty() || !moveQueue.isEmpty()) {
			// 문제의 코드
//			char[][] copyMap = copyMap();
			
			int waterCycle = waterQueue.size();
			for (int i = 0; i < waterCycle; i++) {
				int[] waterQ = waterQueue.poll();
				int waterqX = waterQ[0];
				int waterqY = waterQ[1];
				
				for (int d = 0; d < 4; d++) {
					int nWaterX = waterqX + dx[d];
					int nWaterY = waterqY + dy[d];
					
					if(nWaterX >= 0 && nWaterX < R && nWaterY >= 0 && nWaterY < C) {
						if(map[nWaterX][nWaterY] == '.') {
							waterQueue.add(new int[] {nWaterX, nWaterY});
							map[nWaterX][nWaterY] = '*';
						}
					}
				}
			}
			
			int moveCycle = moveQueue.size();
			for (int i = 0; i < moveCycle; i++) {
				
				int[] moveQ = moveQueue.poll();
				int moveqX = moveQ[0];
				int moveqY = moveQ[1];
				
				for (int d = 0; d < 4; d++) {
					int nMoveX = moveqX + dx[d];
					int nMoveY = moveqY + dy[d];
					
					if(nMoveX == biberX && nMoveY == biberY) {
						System.out.println(visited[moveqX][moveqY]+1);
						System.exit(0);
					}
					
					if(nMoveX >= 0 && nMoveX < R && nMoveY >= 0 && nMoveY < C) {
						if(map[nMoveX][nMoveY] == '.' && visited[nMoveX][nMoveY] == 0) {
							visited[nMoveX][nMoveY] = visited[moveqX][moveqY] + 1;
							moveQueue.add(new int[] {nMoveX, nMoveY});
						}
					}
					
				}
			}
		}
	}
	
	public static char[][] copyMap(){
		char[][] temp = new char[R][C];
		for (int i = 0; i < R; i++) {
			for (int j = 0; j < C; j++) {
				temp[i][j] = map[i][j];
			}
		}
		return temp;
	}
	
	public static void input() throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		st = new StringTokenizer(br.readLine());
		R = Integer.parseInt(st.nextToken());
		C = Integer.parseInt(st.nextToken());

		map = new char[R][C];
		
		for (int i = 0; i < R; i++) {
			String input = br.readLine();
			for (int j = 0; j < C; j++) {
				map[i][j] = input.charAt(j);
				if (map[i][j] == '*') {
					waterQueue.add(new int[] { i, j });
				} else if (map[i][j] == 'S') {
					moveQueue.add(new int[] { i, j });
					map[i][j] = '.';
				} else if (map[i][j] == 'D') {
					biberX = i;
					biberY = j;
				}
			}
		}
	}
}

 

위의 코드에서 큐를 한개를 사용하는 방법도 있다.

참고용으로 보자.

 

풀이2

package SSWtest.BOJ;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Queue;
import java.util.StringTokenizer;

public class BOJ_3055_Pro {
	static int R, C;
	static char[][] map;
	static StringTokenizer st;
	static int[] dr = {-1, 0, 1, 0};
	static int[] dc = {0, 1, 0, -1};
	static Queue<int[]> queue;
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		st = new StringTokenizer(br.readLine());
		R = Integer.parseInt(st.nextToken());
		C = Integer.parseInt(st.nextToken());
		map = new char[R][C];
		
		for (int i = 0; i < R; i++) {
			String input = br.readLine();
			for (int j = 0; j < C; j++) {
				map[i][j] = input.charAt(j);
			}
		}
		
		// 물과 고슴도치를 구분, 좌표
		queue = new ArrayDeque<>();
		
		// 큐에 물 좌표(1), 고슴도치 좌표 넣기(2)
		int[] S = null;
		for (int i = 0; i < R; i++) {
			for (int j = 0; j < C; j++) {
				if 		(map[i][j] == '*') queue.offer(new int[] {i, j, 1});
				else if (map[i][j] == 'S') S = new int[] {i, j, 2};
			}
		}
		
		queue.offer(S);
		
		solution();
	}
	
	public static void solution() {
		
		int time = 0;
		
		while(queue.size() != 0) {
			++time;
			int size = queue.size();
			
			for (int i = 0; i < size; i++) {
				int[] q = queue.poll();
					for (int d = 0; d < 4; d++) {
					int nr = q[0] + dr[d];
					int nc = q[1] + dc[d];
					
					if (nr < 0 || nr >= R || nc < 0 || nc >= C || map[nr][nc] == 'X' || map[nr][nc] == '*') continue;
					if(q[2] == 1) { //물일 때
						if (map[nr][nc] == '.' || map[nr][nc] == 'S') {
							queue.offer(new int[] {nr, nc, 1});
							map[nr][nc] = '*';
						}
					} else { //고슴도치 일 때
						if (map[nr][nc] == 'S') continue; // 자기좌표는 제외
						if (map[nr][nc] == 'D') { // 목적지 비버굴이라면 탐색 종료ㅕ
							System.out.println(time);
							return;
						}
						if (map[nr][nc] == '.') { // 빈 공간
							queue.offer(new int[] {nr, nc, 2});
							map[nr][nc] = 'S';
						}
					}
				}
			}
		}
		System.out.println("KAKTUS"); // 위에서 비버굴을 못찾으면..
	}
}