BOJ G4 4179 불! JAVA

 

4179번: 불!

문제 읽기

문제를 처음 읽었을 땐 별 문제 없이 구현할 수 있을 줄 알았지만.. 자잘한 실수와 문제를 제대로 읽지 않은 게 원인이 되어 조금 헤맸다.

문제 해결

자료구조

char[][] map

Queue 두 개

• 지훈이 이동 Q
• 불 이동 Q

---

실수한 부분

불 퍼지는 방식 이상하게 함

1. 처음에는 이상하게 생각해서 지훈이 큐랑 불 큐랑 두 개 만들고 지훈이 큐에서 하나씩 뺄 때마다 불 큐에서도 하나 빼서 상하좌우 이동함. 결국 depth 다 꼬여서 답 안 나옴
2. 불 퍼지는 걸 for문 + 이차원 배열 복사를 통해서 구현함. 답은 나올 거 같았지만 2퍼센트에서 시간초과가 나옴
3. 불 큐를 다시 부활시키고, 지훈이 큐에서 depth가 바뀔 때마다 불 큐에서 해당 depth의 불만 퍼지게 함. 이때 마지막에 꺼낸 불은 다시 넣어줘야 함!

입력 제대로 체크 안 함

불이 여러 군데에서 들어오는 걸 질문 게시판에서 반례 찾아보면서 알았다.. 이거 해결하니까 11퍼에서 정답으로 나옴

---

코드

package ps.ㄱSolving;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Queue;

public class BOJ_G4_4179_불 {

	static class Pos{
		int r, c;
		int depth;
		public Pos(int r, int c, int depth) {
			super();
			this.r = r;
			this.c = c;
			this.depth = depth;
		}
		@Override
		public String toString() {
			return "Pos [r=" + r + ", c=" + c + ", depth=" + depth + "]";
		}
		
	}
	static char[][] map;
	static int R, C;

	public static void main(String[] args) throws IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		String[] line = in.readLine().split(" ");
		R = Integer.parseInt(line[0]);
		C = Integer.parseInt(line[1]);
		Queue<Pos> fq = new ArrayDeque<>();
		
		Pos start = null;
		map = new char[R][C];
		for (int i = 0; i < R; i++) {
			map[i] = in.readLine().toCharArray();
			for (int j = 0; j < C; j++) {
				if (map[i][j] == 'J') {
					start = new Pos(i, j, 0);
					map[i][j] = '.'; //빈칸임
				}
				else if (map[i][j] == 'F') {
					fq.offer(new Pos(i, j, 0));
				}
			}
		}
		
		//logic : bfs : 지훈이, 불 각각 큐에 넣고..
		/*
		 * 지훈이는 상하좌우로 이동하고 (. 이동 가능, #, F 이동 불가)
		 * 불은 상하좌우로 퍼지고 (. 이동 가능, # 이동 불가)
		 */
		boolean[][] visitedJ = new boolean[R][C];
		
		Queue<Pos> jq = new ArrayDeque<>();
		
		jq.offer(start);
		visitedJ[start.r][start.c] = true; 
		
		int[] dr = {-1, 1, 0, 0};
		int[] dc = {0, 0, -1, 1};
		int saveDepth = -1;
		while(!jq.isEmpty()) {
			//지훈이는 상하좌우로 이동
			Pos curJ = jq.poll();
			
			if (saveDepth != curJ.depth) {
				//불은 상하좌우로 퍼짐
				saveDepth = curJ.depth;
				while(!fq.isEmpty()) {
					Pos curF = fq.poll();

					if (saveDepth != curF.depth) {
						fq.offer(curF); //뺐으니까 다시 넣기..
						break;
					}
					for (int di = 0; di < 4; di++) {
						int nr = curF.r + dr[di];
						int nc = curF.c + dc[di];
						if (nr < 0 || nr >= R || nc < 0 || nc >= C) {
							continue;
						}
						else if (map[nr][nc] == '.') {
							//빈칸일 때만 갈 수 있음
							map[nr][nc] = 'F';
							fq.offer(new Pos(nr, nc, curF.depth+1));
						}
					}
				}
				
			}
			
			for (int di = 0; di < 4; di++) {
				int nr = curJ.r + dr[di];
				int nc = curJ.c + dc[di];
				
				//인덱스 초과하면 종료
				if (nr < 0 || nr >= R || nc < 0 || nc >= C) {
					System.out.println(curJ.depth+1);
					System.exit(0);
				}
				else if (map[nr][nc] == '.' && !visitedJ[nr][nc]) {
					//불이나 벽이 없으면 이동 가능 -> .이면 이동 가능
					visitedJ[nr][nc] = true;
					jq.offer(new Pos(nr, nc, curJ.depth + 1));
				}
			}
		}
		
		System.out.println("IMPOSSIBLE");
	}
}