(JAVA) 백준 3055번 : 탈출

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

3055번: 탈출

 

 

시뮬레이션 문제.

 

 

고슴도치를 이리저리 움직여서 동굴에 들어갈 수 있는 최단 시간을 구하는 문제.

 

 

물, 굴, 돌 이 추가되서 꽤 난이도가 있어보이긴 하지만

 

문제를 유심히 살펴보면

 

전부 고슴도치가 이동할 수 없다는 공통점이 있다.

** 굴은 최종 목적지 이기 때문에 바로 판별할 수 있다.

 

 

또 다른 핵심은

 

여기서 보면

" 물이 찰 예정인 칸으로 이동할 수 없다. " 고 한다.

 

이는 즉 시간이 1초 지났을 때 고슴도치가 이동할 수 없는 곳은

물이 차 있는 곳 + 물의 상하좌우(물이 찰 예정인 칸) 인 곳 + 돌 + 굴 이다.

 

 

마지막으로

시간 초과와 메모리 초과 오류를 방지하기 위해

 

고슴도치가 지나온 자리는 이동할 수 없다 고 판단하는 것이 좋다. (boolean 변경)

 

 

물론 고슴도치가 이전 자리로 되돌아갈 순 있지만

 

다른 DFS나 BFS에서와 마찬가지로

 

최소 시간을 구할 경우 되돌아간다는 것은 이미 최소가 아니기 때문이다.

 

 

 

매커니즘

---

 

초기 설정 값

 

-> 좌표를 표현하기 위해 별도의 클래스를 만들어 사용했다.

*** int[2] 변수를 사용해도 무방하다. 가독성을 위해 클래스를 만들었다.

 

-> 입력값을 담는 char[][]

 

-> 이동 가능 여부를 판단하는 boolean[][]

 

-> 상 - 좌 - 하 - 우 순서대로 좌표 값을 바꾸는 moveX int[], moveY int[]

 

-> 고슴도치가 이동해있는 위치 좌표를 담은 Queue<Point>

 

-> 다음 시간에 물이 흐를 것으로 예상되는 위치 좌표를 담은 Queue<Point>

 

 

 

 

 

알고리즘

1) 고슴도치 시작 지점, 도착 지점(동굴) 좌표 얻음.

 

 

2) 초기 물 좌표 Queue 저장

 

 

3) 초기 고슴도치 시작 좌표 Queue 저장

 

 

4) 0초부터 시작. While(True)

 

*** 물 셋팅

4-1) 물 좌표 Queue에서 하나씩 꺼내며 상하좌우로 물 이동 예상 좌표를 파악한 후 boolean[][] 변경.

 

4-2) 예상 좌표를 새로운 물 좌표 Queue에 넣음

 

4-3) 기존 물 좌표 Queue가 빈다면, 새로운 물 좌표 Queue를 기존 물 좌표 Queue로 복사.

 

 

*** 고슴도치 이동

4-4) 고슴도치 위치 Queue에서 하나씩 꺼내며 상하좌우로 고슴도치 이동 가능 여부를 파악

 

4-5) 도착 지점으로 이동 가능한 경우 현재 시간 + 1 리턴.

 

4-6) 이동 가능한 경우 boolean[][] 변경 후 4-2) 와 동일하게 진행

 

4-7) 시간 1초 증가시킨 후 4) 반복

 

 

5) 결과 출력

 

**** 4) While문에서 반드시 고슴도치가 이동할 수 있는 경우가 없을 때를 따져봐야 한다. (고슴도치 Queue Empty)

**** 그래서 없다면 "KAKTUS" 출력.

 

 

 

감사합니다!

 

다들 화이팅하시고

 

좋은 하루 되세요~! ^_^

 

 

소스코드

---

	import java.io.BufferedReader;
	import java.io.IOException;
	import java.io.InputStreamReader;
	import java.util.LinkedList;
	import java.util.Queue;
	import java.util.StringTokenizer;
	// 탈출 문제
	// 시뮬레이션
	public class p3055 {
	static char[][] map;
	static boolean[][] notMoved; // T : 이동 불가능, F : 이동 가능.
	static Queue<Point3055> waters;
	static int[] moveX = { 0, 1, 0, -1 };
	static int[] moveY = { -1, 0, 1, 0 };
	static int x, y;
	public static void main(String args[]) throws IOException {
	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	StringTokenizer st = new StringTokenizer(br.readLine());
	y = Integer.valueOf(st.nextToken());
	x = Integer.valueOf(st.nextToken());
	map = new char[y][x];
	notMoved = new boolean[y][x];
	waters = new LinkedList<Point3055>();
	// 무조건 D와 S는 하나씩만 주어진다고 했으므로 null로 초기화해도 상관없다.
	Point3055 startPoint = null;
	Point3055 endPoint = null;
	for(int i = 0; i < y; i++) {
	st = new StringTokenizer(br.readLine());
	String line = st.nextToken();
	map[i] = line.toCharArray();
	for(int j = 0; j < x; j++) {
	switch(map[i][j]) {
	case 'D':
	endPoint = new Point3055(j, i);
	notMoved[i][j] = true;
	break;
	case 'S':
	startPoint = new Point3055(j, i);
	break;
	case '*':
	waters.add(new Point3055(j, i));
	notMoved[i][j] = true;
	break;
	case 'X':
	notMoved[i][j] = true;
	break;
	}
	}
	}
	int result = escape(startPoint, endPoint);
	System.out.println(result == -1 ? "KAKTUS" : result);
	}
	// 고슴도치 탈출 함수
	static int escape(Point3055 start, Point3055 end) {
	int time = 0;
	Queue<Point3055> goSumDoChi = new LinkedList<Point3055>();
	goSumDoChi.offer(start);
	while(true) {
	if(goSumDoChi.isEmpty()) {
	return -1;
	}
	// 물 셋팅
	setWaterFlow();
	// 고슴도치 이동시키기
	Queue<Point3055> nextGoSumDoChi = new LinkedList<Point3055>();
	while(!goSumDoChi.isEmpty()) {
	Point3055 goSum = goSumDoChi.poll();
	for(int i = 0; i < moveX.length; i++) {
	int nextX = goSum.x + moveX[i];
	int nextY = goSum.y + moveY[i];
	// 고슴도치가 이동해서 동굴에 도착할 수 있다면
	if(nextX == end.x && nextY == end.y) {
	return time + 1;
	}
	if(validPoint(nextX, nextY)) {
	notMoved[nextY][nextX] = true;
	nextGoSumDoChi.add(new Point3055(nextX, nextY));
	}
	}
	}
	goSumDoChi = nextGoSumDoChi;
	time++;
	}
	}
	// 물 상하좌우로 흐르는 것을 notMoved boolean 배열에 나타내는 함수
	static void setWaterFlow() {
	Queue<Point3055> nextWaters = new LinkedList<Point3055>();
	while(!waters.isEmpty()) {
	Point3055 water = waters.poll();
	for(int i = 0; i < moveX.length; i++) {
	int nextX = water.x + moveX[i];
	int nextY = water.y + moveY[i];
	if(validPoint(nextX, nextY)) {
	notMoved[nextY][nextX] = true;
	nextWaters.add(new Point3055(nextX, nextY));
	}
	}
	}
	waters = nextWaters;
	}
	// 해당 지점에 이동할 수 있는지(물이든 고슴도치이든) 체크하는 함수
	static boolean validPoint(int pointX, int pointY) {
	if(pointX < 0 || pointX >= x) {
	return false;
	}
	if(pointY < 0 || pointY >= y) {
	return false;
	}
	if(notMoved[pointY][pointX]) {
	return false;
	}
	return true;
	}
	}
	class Point3055 {
	int x;
	int y;
	Point3055() {}
	Point3055(int x, int y) {
	this.x = x;
	this.y = y;
	}
	}

view raw p3055.java hosted with ❤ by GitHub