[백준] 3055번 : 탈출 - 자바(JAVA)

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

3055번: 탈출

 

문제 해석

티떱숲의 지도는 R행 C열로 이루어져 있습니다.

 

비어있는 곳은 .

물이 차있는 지역은 *

돌은 X

비버의 굴 D

고슴도치의 위치 S

 

로 표시되어 있습니다.

 

매 분마다 고슴도치는 상하좌우로 한 칸 이동할 수 있습니다.

물도 매분마다 비어있는 칸으로 확장하게 됩니다.

 

물과 고슴도치는 돌을 통과할 수 없습니다.

고슴도치는 물이 차있는 구역으로 이동할 수 없고, 물도 비버의 소굴로 이동할 수 없습니다.

 

고슴도치가 안전하게 비버의 굴로 이동하기 위해 필요한 최소 시간을 구하는 프로그램을 작성하세요

고슴도치는 물이 찰 예정인 칸으로 이동할 수 없습니다.

고슴도치가 만약 비버의 굴로 이동할 수 없다면 "KAKTUS"를 출력합니다.

 

문제 풀이 전 설계

그래프 탐색 문제인 것 같습니다. (BFS or DFS)

최단거리를 찾아야 하므로 BFS

고슴도치는 물이 찰 예정인 칸으로 이동할 수 없으므로 물을 먼저 채우고 고슴도치를 이동하게 해야 합니다.

 

물에 대한 BFS, 고슴도치에 대한 BFS 2개 진행

 

코드

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

class Pos {
	int y;
	int x;

	public Pos(int y, int x) {
		super();
		this.y = y;
		this.x = x;
	}

	@Override
	public String toString() {
		return "Pos [y=" + y + ", x=" + x + "]";
	}

}

public class Main_3055_탈출 {

	static char[][] board;
	static boolean[][] visited;
	// 상하좌우
	static int[] dy = { -1, 1, 0, 0 };
	static int[] dx = { 0, 0, -1, 1 };
	static final int DIRECTION = 4;
	static int R, C, move;
	static Pos detination;
	// 현재 물이 퍼져 나가야 하는 currentWaterQueue
	static Queue<Pos> currentWaterQueue = new LinkedList<Pos>();
	// 다음 물이 퍼져 나가야 하는 nextWaterQueue
	static Queue<Pos> nextWaterQueue = new LinkedList<Pos>();
	// 현재 고슴도치의 임시위치
	static Queue<Pos> currentHedgehogQueue = new LinkedList<Pos>();
	// 다음 고슴도치의 임시위치
	static Queue<Pos> nextHedgehogQueue = new LinkedList<Pos>();

	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());

		board = new char[R][C];
		// visited 대신에 X,*,.으로 구분하면서 맵을 채워가자
		visited = new boolean[R][C];

		// S 는 고슴도치 위치
		// D 는 비버의 굴 위치
		// * 은 물
		// X 는 바위
		// . 비어있음
		for (int y = 0; y < R; y++) {
			String temp = br.readLine();
			for (int x = 0; x < C; x++) {
				board[y][x] = temp.charAt(x);
				if (board[y][x] == 'S') {
					currentHedgehogQueue.add(new Pos(y, x));
					visited[y][x] = true;
				}
				if (board[y][x] == 'D') {
					detination = new Pos(y, x);
				}
				if (board[y][x] == '*') {
					currentWaterQueue.add(new Pos(y, x));
				}
			}
		}
		while (true) {
			waterBFS();
			if (hedgehogBFS()) {
				break;
			}
		}

	}

	private static void waterBFS() {
		while (!currentWaterQueue.isEmpty()) {
			Pos temp = currentWaterQueue.poll();
			int y = temp.y;
			int x = temp.x;

			for (int k = 0; k < DIRECTION; k++) {
				int tempY = y + dy[k];
				int tempX = x + dx[k];
				if (!isPosValid(tempY, tempX)) {
					continue;
				}
				if (!isWaterFeatureValid(tempY, tempX)) {
					continue;
				}
				board[tempY][tempX] = '*';
				nextWaterQueue.add(new Pos(tempY, tempX));
			}
		}
		// CQ -> A
		// NQ -> B
		currentWaterQueue = nextWaterQueue;
		// CQ -> B
		// 메모리 leak이 발생하진 않을까?
		nextWaterQueue = new LinkedList<Pos>();
		// NQ -> C

	}

	private static boolean hedgehogBFS() {
		while (!currentHedgehogQueue.isEmpty()) {
			Pos temp = currentHedgehogQueue.poll();
			int y = temp.y;
			int x = temp.x;

			for (int k = 0; k < DIRECTION; k++) {
				int tempY = y + dy[k];
				int tempX = x + dx[k];
				if (!isPosValid(tempY, tempX)) {
					continue;
				}
				if (!isHedgehogFeatureValid(tempY, tempX)) {
					continue;
				}
				if (visited[tempY][tempX]) {
					continue;
				}
				visited[tempY][tempX] = true;
				nextHedgehogQueue.add(new Pos(tempY, tempX));
			}
		}
		// 고슴도치가 이동할 수 없다면? nextHedgehogQueue == empty
		if (nextHedgehogQueue.isEmpty()) {
			System.out.println("KAKTUS");
			return true;
		}
		move++;
		for (Pos e : nextHedgehogQueue) {
			if (e.x == detination.x && e.y == detination.y) {
				System.out.println(move);
				return true;
			}
		}
		// CQ -> A
		// NQ -> B
		currentHedgehogQueue = nextHedgehogQueue;
		// CQ -> B
		// 메모리 leak이 발생하진 않을까?
		nextHedgehogQueue = new LinkedList<Pos>();
		return false;
	}

	private static boolean isPosValid(int tempY, int tempX) {
		return (tempY >= 0 && tempX >= 0 && tempY < R && tempX < C);
	}

	private static boolean isWaterFeatureValid(int tempY, int tempX) {
		char feature = board[tempY][tempX];
		return feature != 'X' && feature != '*' && feature != 'D';
	}

	private static boolean isHedgehogFeatureValid(int tempY, int tempX) {
		char feature = board[tempY][tempX];
		return feature != 'X' && feature != '*';
	}

}