[백준 3055] 탈출 (자바)

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

3055번: 탈출

 

난이도 : 골드 5

 

BFS로 어렵지 않게 풀 수 있는 문제였습니다.

주의해야 할 것은 물이 불어날 위치는 못 간다는 것입니다.

그래서 고슴도치가 이동하기 전에 미리 물을 불려놓고 고슴도치를 이동시켰습니다.

 

---

전역 변수 

r, c = 티떺숲의 크기

answer = 이동 시간

endX, endY = 비버 굴의 좌표값

startX, startY = 고슴도치의 시작 위치

map[][] = 티떺숲의 상태 값

visit[][] = 고슴도치가 방문한 곳을 check한 배열

dx[], dy[] = 상, 하, 좌, 우를 이동할 수 있게 만든 배열

q = 고슴도치가 이동할 수 있는 좌표를 저장하는 큐

메소드

void main 

입력을 받고 비버 굴의 위치와 고슴도치의 위치를 각 변수에 저장합니다.(run 호출)

void run

고슴도치가 이동할 수 있는 곳으로 이동합니다. Queue를 이용한 BFS로 구현했습니다.

고슴도치가 한 번 이동할 수 있는 거리를 이동하면(각 좌표에서 상, 하, 좌, 우)

시간이 1 증가하고 물도 불어나야 합니다.

Queue에 -1, -1을 넣고 poll값이 -1, -1이 나오면 물이 불어나고, 시간이 증가하도록 했습니다.

예를 들어 고슴도치가 4방향으로 이동 가능하다면 큐에 4방향의 좌표와 -1, -1이 들어갑니다.

다음으로 4방향으로 이동한 고슴도치가 이동할 수 있는 곳이 총 8개라고 한다면 

큐에 8개의 좌표값과 -1, -1이 들어가서 큐의 사이즈는 9가 되는 것입니다.

비버의 굴을 만나면 시간을 출력하고 비버의 굴을 만나기 전에 큐가 비워졌으면 "KAKTUS"를 출력합니다.

(water, next호출)

void water

물이 불게 합니다. 만약 map에 직접적으로 물이 불도록 한다면 각 방향으로 1칸이 아닌 

map 전체가 물바다가 되는 일이 발생할 수도 있습니다. 

그래서 map을 검사하여 temp배열에 임시로 물을 불게 한 후 temp배열의 값을 map으로 가져왔습니다.

굳이 배열을 하나 더 만들지 않고 List, Queue 등으로도 해결할 수 있습니다.

(check호출)

void next

파라미터로 현재 고슴도치의 위치가 주어집니다.

run 메소드에서 고슴도치가 갈 수 있는 방향을 찾기 위해 호출됩니다.

고슴도치가 갈 수 있는 곳, 방문하지 않았던 곳을 큐에 넣습니다.

(check호출)

boolean check

좌표값이 유효한 값인지 알려줍니다.

class Point

고슴도치의 좌표값을 가집니다. x, y

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

public class p3055 {
	static int r, c, answer, endX=0, endY=0, startX=0, startY=0;
	static char map[][];
	static boolean visit[][];
	static int dx[] = {-1,1,0,0};
	static int dy[] = {0,0,-1,1};
	static Queue<Point> q;

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer stz = new StringTokenizer(br.readLine());
		r = Integer.parseInt(stz.nextToken());
		c = Integer.parseInt(stz.nextToken());
		answer = 0;
		map = new char[r][c];
		visit = new boolean[r][c];
		q = new LinkedList<Point>();

		for(int i = 0; i < r; i++) {
			String s = br.readLine();
			for(int j = 0; j < c; j++) {
				map[i][j] = s.charAt(j);
				if(map[i][j] == 'D') {
					endX = i;
					endY = j;
				}
				else if(map[i][j] == 'S') {
					startX = i;
					startY = j;
				}
			}
		}

		run();
	}

	public static void run() {
		q.add(new Point(-1, -1));
		q.add(new Point(startX, startY));

		while(!q.isEmpty()) {
			Point point = q.poll();
			
			if(point.x == -1) {
				water();
				answer++;
				if(!q.isEmpty())
					q.add(point);
				continue;
			}

			if(point.x == endX && point.y == endY) {
				System.out.println(answer-1);
				return;
			}

			next(point.x, point.y);
		}

		System.out.println("KAKTUS");
	}

	public static void water() {
		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];

		for(int i = 0; i < r; i++) {
			for(int j = 0; j < c; j++) {
				if(map[i][j] == '*') {
					for(int k = 0; k < 4; k++) {
						int nx = i + dx[k];
						int ny = j + dy[k];

						if(check(nx, ny) && (map[nx][ny] == '.' || map[nx][ny] == 'S'))
							temp[nx][ny] = '*';
					}
				}
			}
		}

		for(int i = 0 ; i < r; i++)
			for(int j = 0; j < c; j++)
				map[i][j] = temp[i][j];
	}

	public static void next(int x, int y) {
		for(int i = 0; i < 4; i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];
			if(check(nx, ny) && !visit[nx][ny] && (map[nx][ny] == '.' || map[nx][ny] == 'D')) {
				visit[nx][ny] = true;
				q.add(new Point(nx, ny));
			}
		}
	}

	public static boolean check(int x, int y) {
		return x >= 0 && y >= 0 && x < r && y < c;
	}

	static class Point{
		int x, y;
		Point(int x, int y){
			this.x = x;
			this.y = y;
		}
	}
}