[백준] 4179번: 불!

🔍 문제 읽기

4179번: 불!

입력	출력
R(행)과 C(열) R x C 미로의 정보 (#: 벽, J: 지훈, F: 불, .: 이동 가능 공간)	미로를 탈출할 수 있는 경우 ➡︎ 가장 빠른 탈출시간을 출력 미로를 탈출 할 수 없는 경우 ➡︎ IMPOSSIBLE 을 출력
4 4 #### #JF# #..# #..#	3

 

 

 

💡풀이 

👩‍💻 사용언어 : cpp

 

❗️[핵심] 다차원 배열에서의 BFS (너비 우선)

👉 BFS는 너비 우선이기에 최단시간을 구할 수 있다.

 

 

❗️ 문제 풀이 아이디어

0️⃣ 불과 지훈이의 이동에 대한 시간 정보 필요! 

지훈이와 불을 분리하여 미로의 칸에 따른 이동 시간을 표에 나타냈다.

 

미로의 각 칸에 대하여

지훈이가 불 보다 빠른 시간 내에 도달하면 이동할 수 있다.

지훈이가 불 보다 늦으면 해당 칸으로 이동은 불가하다.

 

위의 정보를 종합하여 지훈이와 불이 먼저 점령하는 칸에 대해 표로 나타냈다.

지훈이의 가장 빠른 탈출 시간은 3이다.

 

각 칸에 대하여 fire 시간 ≤ 지훈이 시간 의 경우, 해당 칸은 지훈이가 지나갈 수 없다 는 점을 이용하자.

 

 

1️⃣  불에 대한 BFS를 수행

 불에 대해 BFS를 먼저 수행하여 시간정보를 fire 배열에 저장하자.

 

 

2️⃣ 지훈이에 대한 BFS를 수행

그 다음 지훈이에 대해 BFS를 수행한다.

이때 기존의 조건에서"fire 시간 ≤ 지훈이 배열의 시간 의 경우 해당 칸은 지훈이가 지나갈 수 없다"는 조건을 추가하자.

 

 

3️⃣ 탈출 성공 : 지훈이가 불과 만나지 않고 미로 밖으로 빠져나감

지훈이가 미로 바깥 범위로 가장 처음 나가는 경우의 시간을 출력하고 모든 작업을 종료하자!

지훈이가 범위 밖으로 나갈 경우의 조건을 추가하자!

 

 

4️⃣ 탈출 실패 : 큐가 빌 때 까지 3️⃣의 조건에서 종료하지 못하면 IMPOSSIBLE을 출력

큐가 빌 때 까지 3️⃣의 조건에서 걸려 시간을 출력하지 못한다면,

그 상황은 지훈이가 미로에서 탈출하지 못한 경우(불 때문에 이동 불가, 벽에 가로막혀 탈출 불가 등)이다.

 

 

 

 

 

🧩 코드

1️⃣ 필요한 배열 선언

board 배열은 미로의 정보를 저장한다.

fire 배열은 BFS를 수행하여 불의 이동 시간을 저장할 배열이다.

jihun 배열은 BFS를 수행하여 지훈이의 이동 시간을 저장할 배열이다.

 

2️⃣ 불과 지훈이에 대한 큐 선언과 배열 초기화

 

 

3️⃣ 미로 입력 & 각 큐에 불과 지훈이의 위치 정보 넣기

미로를 입력하면서 불과 지훈이의 위치정보를 ①큐에 넣고 ②방문 흔적을 남긴다.

 

 

4️⃣ 불 BFS

①벽, ②이미 지나간 경로, ③미로 바깥 영역

세가지 조건에 대해 불은 이동할 수 없다.

 

 

4️⃣ 지훈 BFS 와 답 출력

①벽, ②이미 지나간 경로, ③불이 먼저 도달한 칸

세가지 조건에 대해 지훈이는 이동할 수 없다.

 

지훈이가 미로 바깥 영역으로 나갔다면 그 순간이 가장 빠른 탈출 시간이기에

바로 "미로 바깥으로 나가기 한칸 전 시간 + 1"을 출력하고 종료한다.

 

큐가 빌 때 까지 어떠한 시간도 출력하지 못함은 지훈이가 탈출하지 못했음을 의미한다.

IMPOSSIBLE을 출력한다.

 

 

🔥 완성 코드

 

 

재미있는 문제다.

처음 풀 때는 지훈이를 불에 8번이나 떨궜지만..

조건을 잘 체크해야하는 문제였다.