[Baekjoon] 백준 3055 탈출 (G4 / BFS, 던전) - Java

링크

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

3055번: 탈출

 

 

 

 

문제 해석

맵 크기 : R * C
비어있는 곳 : .
물이 차있는 곳 : *
돌 : X
비버 : D
고슴도치 : S

 

고슴도치가 비버에게로 도착해야 함
매턴 물은 인접한 빈칸을 채움
고슴도치는 물이 있는 곳을 건널 수 없음
물은 돌이나 비버의 집을 채울 수 없음

 

- 입력
첫 번째 줄 : R C  # 세로 가로
나머지 줄 : 던전 정보

 

- 출력
건널 수 있다면 숫자
건널 수 없다면 KAKTUS

 

 

 

 

풀이 & 코드 해석

BFS로 풀 수 있는 던전 문제입니다.

 

던전 문제에서 한 턴에 동시에 움직이는 경우 (비버와 물) 어떤 것을 먼저 움직여야 할지를 정하는 것이 가장 중요합니다.

 

해당 문제의 경우 문제 내부에서 물을 먼저 이동한다라고 언급이 되어 있으므로 물을 먼저 이동하시면 해결 가능합니다.

 

 

물이나 고슴도치 모두 지나온 길을 지도에 찍고 이동하므로 별도의 방문 배열은 사용하지 않았습니다.

 

 

 

 

코드

package day05;

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

public class 탈출 {

	static char map[][];

	static Queue<Point> q = new LinkedList<>();

	static int R, C;

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		R = Integer.parseInt(st.nextToken());
		C = Integer.parseInt(st.nextToken());

		map = new char[R][C];

		Point S = null; // 고슴도치 위치 저장 변수

		for (int i = 0; i < R; i++) {
			st = new StringTokenizer(br.readLine());
			String s = st.nextToken();
			for (int j = 0; j < C; j++) {
				map[i][j] = s.charAt(j);

				// 고슴도치라면
				if (map[i][j] == 'S') {
					S = new Point(i, j, 0, 'S');
				}

				// 물이라면
				if (map[i][j] == '*') {
					q.offer(new Point(i, j, 0, '*'));
				}

			}
		}
		// 고슴도치를 가장 마지막에 넣음
		q.offer(S);

		int answer = bfs();

//		print(map);
		System.out.println(answer == 0 ? "KAKTUS" : answer);

	}

	static int[] dx = { -1, 0, 1, 0 };
	static int[] dy = { 0, 1, 0, -1 };

	private static int bfs() {
		while (!q.isEmpty()) {
			Point p = q.poll();

			for (int d = 0; d < dx.length; d++) {
				int nx = p.x + dx[d];
				int ny = p.y + dy[d];

				if (nx >= 0 && nx < R && ny >= 0 && ny < C && map[nx][ny] != 'X' && map[nx][ny] != '*') {
					// 물의 경우
					if (p.chara == '*') {
						// 물, 돌, 비버집이 아닌 경우
						if (map[nx][ny] == '.' || map[nx][ny] == 'S') {
//							print(map);
							q.offer(new Point(nx, ny, p.level + 1, '*'));
							map[nx][ny] = '*';
						}
					}

					// 고슴도치의 경우
					if (p.chara == 'S') {
						// 비버집 이라면
						if (map[nx][ny] == 'D') {
//							print(map);

							return p.level + 1;
						}
						// 빈칸 이라면
						if (map[nx][ny] == '.') {
							map[nx][ny] = 'S';
							q.offer(new Point(nx, ny, p.level + 1, 'S'));
//							print(map);

						}

					}
				}
			}
		}
		return 0;
	}

	static class Point {
		int x;
		int y;
		int level; // 이동하는데 걸린 시간
		char chara; // 고슴도치 또는 물을 저장

		public Point(int x, int y, int level, char chara) {
			this.x = x;
			this.y = y;
			this.level = level;
			this.chara = chara;
		}
	}

	private static void print(char[][] map) {
		for (int i = 0; i < map.length; i++) {
			for (int j = 0; j < map[i].length; j++) {
				System.out.print(map[i][j] + " ");
			}
			System.out.println();
		}

	}

}

 

 

 

 

발생한 문제 & 해결 방안

고슴도치를 이동할 때 맵에 찍고 이동하지 않아서 메모리 초과 문제가 발생하였다.

 

아는 문제라고 할 지라도 긴장하고 틀리지 않도록 노력하자!

 

 

 

 

 

 

 

해당 코드는 에디터가 코드 연습을 위해 직접 작성하였습니다.

혹시 오류가 있거나 더 좋은 코드 방향성을 아시는 분은 댓글로 남겨주시면 감사하겠습니다!

python source : https://github.com/ssh5212/conding-test-practice

java source : https://github.com/ssh5212/coding-test-java