[BJ3055] 탈출

 백준 - 탈출 

문제 링크

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

3055번: 탈출

 

문제 입출력

5 5
D...*
..XXX
.....
.....
.S...

5

 

문제 풀이

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


public class Main {
	static int ans, R, C;
	static char[][] map;
	static boolean[][] visit;

	// 상하좌우
	static int[] dy = { -1, 1, 0, 0 };
	static int[] dx = { 0, 0, -1, 1 };

	static Queue<Node> gq = new ArrayDeque<>(); // 고슴도치
	static Queue<Node> wq = new ArrayDeque<>(); // 물


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

		// 초기화
		ans = Integer.MAX_VALUE;
		gq.clear();
		wq.clear();
		visit = new boolean[R][C];

		map = new char[R][C];
		for (int i = 0; i < R; i++) {
			String line = br.readLine();
			for (int j = 0; j < C; j++) {
				char m = map[i][j] = line.charAt(j);
				if (m == 'S') {
					gq.offer(new Node(i, j, 0));
					visit[i][j] = true;
				} else if (m == '*') wq.offer(new Node(i, j, 0));

			}

		}

		// 탐색
		bfs();

		// 출력
		if (ans == Integer.MAX_VALUE) System.out.println("KAKTUS");
		else System.out.println(ans);

	} // end main


	private static void bfs() {
		while (!gq.isEmpty()) {
			// 물 차오르기
			int size = wq.size();
			for (int i = 0; i < size; i++) {
				Node water = wq.poll();
				int y = water.y;
				int x = water.x;

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

					if (ny < 0 || ny >= R || nx < 0 || nx >= C) continue;
					if (map[ny][nx] == 'X') continue;
					if (map[ny][nx] == '*') continue;
					if (map[ny][nx] == 'D') continue;

					wq.offer(new Node(ny, nx, water.d + 1));
					map[ny][nx] = '*';

				}

			}

			// 고슴도치 이동
			size = gq.size();
			for (int i = 0; i < size; i++) {
				Node dochi = gq.poll();
				int y = dochi.y;
				int x = dochi.x;

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

					if (ny < 0 || ny >= R || nx < 0 || nx >= C) continue;
					if (visit[ny][nx]) continue;

					if (map[ny][nx] == 'D') {
						ans = Math.min(ans, dochi.d + 1);
						return;
					}

					if (map[ny][nx] == '.') {
						gq.offer(new Node(ny, nx, dochi.d + 1));
						visit[ny][nx] = true;
						map[y][x] = '.';
						map[ny][nx] = 'S';
					}

				}

			}

		}

	} // end bfs


	static class Node {
		int y, x;
		int d;


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


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

	} // end Node
}

• 물이 먼저 차오른 다음에 고슴도치가 이동한다.
• 물과 고슴도치는 1초마다 움직이므로 depth 마다 움직여야 한다. 따라서 size 만큼 돌아야한다.
• 물은 visit 체크를 하지 않아도 되지만 (이미 * 인 것은 continue 해주면 되므로)
• 고슴도치는 visit 체크를 하지 않으면 자기가 왔던 곳에 다시 내려갈 수 있기 때문에 메모리 초과가 발생하여 visit 체크를 해줘야한다.

 

 

 

 

 

 

 

 

 

# BJ 탈출 # 백준 탈출 java

---