BOJ(백준) 4179[불!]

백준 4179번 문제인 “불!” 문제를 해결하는 방법에 대해 작성해 보겠습니다. 이 문제는 미로에서 불과 지훈(Jihoon)이 이동할 수 있는 최단 경로를 찾는 문제로, BFS(너비 우선 탐색)를 사용하여 해결할 수 있습니다. 문제를 분석하고 접근 방법을 정리한 후, 최종적인 정답 코드를 확인해 보겠습니다.

문제 URL : https://www.acmicpc.net/problem/4179

1. 문제 설명

1) 문제 개요
주어진 미로에서 불과 지훈의 위치가 주어지며, 지훈이 미로를 탈출할 수 있는지 여부와 탈출할 수 있다면 그 시간을 구하는 문제입니다. 미로는 벽('#'), 통로('.'), 지훈의 초기 위치('J'), 불의 초기 위치('F')로 이루어져 있습니다.

2) 입력
• 첫 번째 줄: 미로의 행의 수  R  (1 ≤ R ≤ 1000)과 열의 수  C  (1 ≤ C ≤ 1000)
• 다음  R 개의 줄: 미로의 각 행에 대한 정보

3) 출력
• 지훈이 탈출할 수 있다면 탈출하는 데 걸리는 최소 시간을 출력합니다.
• 탈출할 수 없다면 "IMPOSSIBLE"을 출력합니다.

2. 접근법

1) 입력받기

• sys.stdin.readline을 사용하여 빠르게 입력을 받습니다.

• 미로 정보를 2차원 리스트로 저장하고, 지훈과 불의 초기 위치를 따로 저장합니다.

 

2) BFS를 활용한 탐색

• 불의 이동과 지훈의 이동을 각각 BFS로 구현합니다.

• 불의 확산은 모든 지점에서 동시에 일어나므로, 불의 BFS를 먼저 수행하여 각 위치까지 도달하는데 걸리는 시간을 계산합니다.

• 이후 지훈의 BFS를 수행하면서, 불의 도달 시간보다 먼저 도달할 수 있는지 검사합니다.

 

3) 결과 출력

• 지훈이 미로의 경계에 도달하면 탈출할 수 있으며, 이 경우 이동한 거리를 출력합니다.

• 모든 경우를 탐색한 후에도 탈출할 수 없으면 "IMPOSSIBLE"을 출력합니다.

3. 정답 코드

import sys
input = sys.stdin.readline

# 입력받은 행(R)과 열(C)의 크기
R, C = map(int, input().split())
arr = []
for _ in range(R):
    arr.append(list(input().rstrip()))  # 각 행을 리스트로 저장

# 이동 방향을 나타내는 델타 배열 (동, 서, 남, 북)
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]

# 불(fire)과 지훈(Jihoon)의 이동 거리 기록 배열
fDist = [[0] * C for _ in range(R)]
jDist = [[0] * C for _ in range(R)]

# 지훈과 불의 시작 위치를 저장할 리스트
j = []
f = []

# 지훈과 불의 초기 위치 설정
for r in range(R):
    for c in range(C):
        if arr[r][c] == 'J':    # 지훈의 초기 위치
            jDist[r][c] = 1     # 초기 위치에서의 거리를 1로 설정
            j.append((r, c))    # 지훈의 위치 추가
        if arr[r][c] == 'F':    # 불의 초기 위치
            fDist[r][c] = 1     # 초기 위치에서의 거리를 1로 설정
            f.append((r, c))    # 불의 위치 추가

# 불의 BFS (너비 우선 탐색)
while f:
    r, c = f.pop(0)
    for i in range(4):
        nx = r + dx[i]
        ny = c + dy[i]
        if 0 <= nx < R and 0 <= ny < C:
            if fDist[nx][ny] == 0 and arr[nx][ny] != '#':  # 방문하지 않은 곳
                fDist[nx][ny] = fDist[r][c] + 1  # 이동 거리 갱신
                f.append((nx, ny))  # 새로운 불 위치 추가

# 지훈의 BFS (너비 우선 탐색)
while j:
    r, c = j.pop(0)
    for i in range(4):
        nx = r + dx[i]
        ny = c + dy[i]
        if not (0 <= nx < R and 0 <= ny < C):  # 지훈이 탈출 가능한 경우
            print(jDist[r][c])  # 현재까지의 이동 거리 출력
            sys.exit()          # 프로그램 종료
        if 0 <= nx < R and 0 <= ny < C:
            if jDist[nx][ny] == 0 and arr[nx][ny] != '#':  # 방문하지 않은 곳
                if fDist[nx][ny] > jDist[r][c] + 1 or fDist[nx][ny] == 0:  
                    # 불보다 먼저 도착 가능 혹은 불이 퍼지지 않는 경우
                    jDist[nx][ny] = jDist[r][c] + 1     # 이동 거리 갱신
                    j.append((nx, ny))                  # 새로운 지훈 위치 추가

# 지훈이 탈출할 수 없는 경우
print('IMPOSSIBLE')

 

4. 코드 설명

1) 입력 받기

• R, C는 미로의 행과 열의 수를 의미하며, arr 리스트에 미로의 각 행을 저장합니다.

• 미로의 각 요소는 벽(#), 통로(.), 지훈의 위치(J), 불의 위치(F)로 구성됩니다.

 

2) 초기화

• dx와 dy는 동, 서, 남, 북 방향을 나타내는 델타 배열로, BFS 탐색 시 사용됩니다.

• fDist와 jDist는 각각 불과 지훈의 이동 거리를 기록하기 위한 2차원 배열입니다. 초기에는 모든 거리가 0으로 설정되어 있습니다.

• j와 f는 각각 지훈과 불의 시작 위치를 저장하는 리스트입니다.

 

3) BFS를 이용한 탐색

• 불의 BFS: 불이 퍼지는 속도를 먼저 계산하여 fDist에 기록합니다. 불이 방문하지 않은 곳이나 벽이 아닌 곳에 대해 이동 거리를 갱신하며 BFS를 진행합니다.

• 지훈의 BFS: 지훈이 탈출 가능한지 확인하며, 불보다 먼저 도착할 수 있는지 검사합니다. 탈출 가능한 경우 이동 거리를 출력하고 프로그램을 종료합니다. 만약 모든 경로를 탐색해도 탈출하지 못한다면 "IMPOSSIBLE"을 출력합니다.

 

[순서도]

1. 미로 정보 입력 및 초기화

     ↓

2. 불의 BFS 수행

     ↓

3. 지훈의 BFS 수행

     ↓

4. 탈출 가능한지 확인

     ↓

(Yes) 탈출 가능 → 탈출 시간 출력

     ↓

(No) 탈출 불가 → "IMPOSSIBLE" 출력

5. Github으로 확인

coTest/BOJ/BOJ01_10_01_4179.py at main · pcy4196/coTest