[Java Algorithm] 탈출 BOJ #3055

문제

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

3055번: 탈출

 

내 문제 풀이

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.StringTokenizer;

public class BOJ_3055 {

	static int r, c;
	static char[][] map;
	static int[] start;
	static Deque<int[]> que = new ArrayDeque<>();
	static int[] dx = {0, 0, -1, 1};
	static int[] dy = {-1, 1, 0, 0};

	public static int bfs() {
		while(!que.isEmpty()) {
			int[] now = que.removeFirst();
			int x = now[0];
			int y = now[1];
			int check = now[2]; // 물인지 고슴도치인지 판단 (물 == 0, 고슴도치 == 1)
			int cnt = now[3];

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

				if(nx < 0 || ny < 0 || nx >= r || ny >= c) continue;
				if(check == 1 && map[nx][ny] == 'D') {
					return cnt+1;
				}
				if(map[nx][ny] != '.') continue;

				if(check == 0) map[nx][ny] = '*';
				if(check == 1) map[nx][ny] = 'S';
				que.add(new int[]{nx, ny, check, cnt+1});
			}
		}
		return -1;
	}

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

		st = new StringTokenizer(in.readLine());
		r = Integer.parseInt(st.nextToken());
		c = Integer.parseInt(st.nextToken());
		map = new char[r][c];

		for(int i = 0; i < r; i++) {
			String str = in.readLine();
			for(int j = 0; j < c; j++) {
				map[i][j] = str.charAt(j);
				if(map[i][j] == '*') que.add(new int[]{i, j, 0, 0}); // 물의 위치 큐에 추가
				else if(map[i][j] == 'S') start = new int[]{i, j, 1, 0}; // 고슴도치 위치 일단 저장
			}
		}
		que.add(start); // 고슴도치를 물 이동 후 움직이기 위해 마지막에 추가

		int ans = bfs();
		System.out.println(ans == -1 ? "KAKTUS" : ans);
	}
}

👉 BFS 문제

• 주어지는 지도의 정보를 받으면서, 물이나 고슴도치가 입력된 경우를 조건처리했다.
  고슴도치는 물이 찰 예정인 칸으로 이동할 수 없으므로, 물 먼저 이동 후 고슴도치를 이동시키고자
  물이 입력된 경우 바로 que에 추가해주었고, 고슴도치는 start 변수에 저장 후 마지막에 추가했다.
  이 때, 물의 경우 que에 추가하는 int 배열의 세 번째 요소를 0으로, 고슴도치는 1로 만들어서 추가했다.
• bfs 메서드에서는 첫 번째 요소부터 꺼내어 탐색했는데,
  고슴도치이면서, 앞으로 탐색하려는 자리가 'D'일 경우 탈출에 성공한 것으로 판단해주었다.
  그리고 앞으로 탐색하려는 자리가 '.'이 아니라면 그 자리로는 갈 수 없으므로 continue 했다.
• 발생 가능한 예외를 모두 패스했다면 앞으로 탐색하려는 자리에 물, 혹은 고슴도치를 확산시켜주었다.
  그리고 que에 해당하는 자리를 새로운 시작점으로 추가했다.

 

💡 피드백

• https://seolhee2750.tistory.com/222 이 문제와 굉장히 비슷했음!!