BOJ 5427 불

www.acmicpc.net/problem/5427

5427번: 불

 

 

문제 분석

- 어제 풀었던 벽 부수고 이동하기 문제(BOJ 1442 벽 부수고 이동하기 2)와 비슷하다고 생각하면 큰 착각이다.❌(물론 착각해서 이 문제도 3차원 배열 선언해둔건 비밀이다) 벽 부수기의 경우 변화하는 변수에 따라 visited판단을 해줘야하는 반면에 이 문제는 상근이의 이동과 불의 이동을 구분해서 처리해줘야한다. 즉 visited체크는 같이 해준다. 

cf) 문제에서 불이 번질 예정인 곳에 상근이가 갈 수 없기때문에 불을 먼저 질러준 다음 상근이를 이동시켰다.

 

 

문제 풀이

1) 상근이의 위치를 sDq에 입력받는다. 불의 위치는 fDq에 입력받는다.

- 상근이의 위치를 입력받았을 경우 방문처리해준다. (결과적으로 해당 문제는 상근이의 이동으로 종료나 visited 판단해야하기 때문이다)

2) 각각의 입력이 종료되면 bfs탐색을 한다.

3) bfs는 주체를 상근이로 하여 이동이 종료되면(sDq가 비었을 경우) 도달하지 못한 것이다.

4) 상근이가 돌아다닐 수 있는 만큼 while문을 돌리고 해당 while문 안에서 불을 지르고 상근이를 이동시키는 순서대로 코드를 구현한다.

5) 불을 지를 땐 불이 있는 위치를 전부 받아와서 각각의 위치에서 상하좌우에 있는 위치에 불을 지르고, 해당 좌표를 fDq에 넣어 다음 방문을 위한 처리를 해준다.

6) 불을 질렀다면 상근이를 이동시킨다. 상근이의 위치에서 상하좌우로 이동시켜보고 이동시켰을 경우 좌표에서 벗어나면 해당 함수를 벗어난다. (여기서 로직을 잘못 세워서 오류가 났었다😂) 

7) 만약 아직 벗어날 준비가 되지 않았다면 다음 이동 경로를 체크하여 sDq에 값을 넣고 다음 이동을 위한 처리를 해준다. 이 때도 방문 처리를 잊으면 안된다.

 

 

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

public class Main {
	private static int tc, ans, w, h;
	private static char[][] map;
	private static boolean[][] visited;
	private static int[] dr = { -1, 1, 0, 0 };
	private static int[] dc = { 0, 0, -1, 1 };
	private static Deque<fPoint> fDq = new ArrayDeque<>(); // 불의 위치 담을 큐
	private static Deque<sPoint> sDq = new ArrayDeque<>(); // 상근이의 위치 담을 큐

	private static void bfs() {

		while (!sDq.isEmpty()) {

			// 불지르기
			int size = fDq.size();
			for (int i = 0; i < size; i++) {
				fPoint cur = fDq.poll();
				int r = cur.x;
				int c = cur.y;

				for (int d = 0; d < 4; d++) {
					int nr = r + dr[d];
					int nc = c + dc[d];

					if (nr >= 0 && nc >= 0 && nr < h && nc < w && map[nr][nc] == '.') {
						map[nr][nc] = '*';
						fDq.add(new fPoint(nr, nc));
					}
				}
			} // 불지르기 마무리

			// 상근이 이동시키기
			size = sDq.size();
			for (int i = 0; i < size; i++) {
				sPoint cur = sDq.poll();
				int r = cur.x;
				int c = cur.y;
				int cnt = cur.depth;

				for (int d = 0; d < 4; d++) {
					int nr = r + dr[d];
					int nc = c + dc[d];

					if (nr < 0 || nc < 0 || nr == h || nc == w) {
						ans = cnt + 1;
						sDq.clear();
						return;
					}

					if (visited[nr][nc])
						continue;

					if (map[nr][nc] == '.') {
						visited[nr][nc] = true;
						sDq.add(new sPoint(nr, nc, cnt + 1));
					}
				}
			} // 상근이 이동 끝

		} // 전체 bfs
	}// bfs

	private static void input() throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		tc = Integer.parseInt(br.readLine());
		StringTokenizer st;
		for (int T = 0; T < tc; T++) {
			fDq.clear();
			sDq.clear();
			ans = 0;
			st = new StringTokenizer(br.readLine());
			w = Integer.parseInt(st.nextToken());
			h = Integer.parseInt(st.nextToken());

			map = new char[h][w];
			visited = new boolean[h][w];

			for (int i = 0; i < h; i++) {
				String s = br.readLine();
				for (int j = 0; j < w; j++) {
					char ch = s.charAt(j);
					map[i][j] = ch;
					if (ch == '*') {
						fDq.add(new fPoint(i, j));
					}
					if (ch == '@') {
						sDq.add(new sPoint(i, j, 0));
						visited[i][j] = true;
					}
				}
			}

			bfs();
			System.out.println(ans == 0 ? "IMPOSSIBLE" : ans);
		}

	}// input

	public static void main(String[] args) throws NumberFormatException, IOException {
		input();
	}// main

	static class fPoint {
		int x;
		int y;

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

	static class sPoint {
		int x;
		int y;
		int depth;

		public sPoint(int x, int y, int depth) {
			super();
			this.x = x;
			this.y = y;
			this.depth = depth;
		}
	}
}