[BOJ#4179] 불! (Python) bfs 턴제개념, append() - extend() 차이

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

 

r, c= map(int, input().split())
arr = []
for i in range(r):
    arr.append(list(input()))

# print(arr)
di, dj = [0, 1, -1, 0], [1, 0, 0, -1]
def escape(fire):
    q = []
    q.append((ji, jj, 0))
    fire_q = []
    fire_q.extend(fire)
    visited = [[False] * c for _ in range(r)]
    visited[ji][jj] = True

    while q:
        fire_size = len(fire_q)
        for _ in range(fire_size):
            ci, cj = fire_q.pop(0)
            for k in range(4):
                ni, nj = ci + di[k], cj + dj[k]
                if 0 <= ni < r and 0 <= nj < c and arr[ni][nj] != 'F' and arr[ni][nj] != '#':
                    arr[ni][nj] = 'F'
                    fire_q.append((ni, nj))
        
        q_size = len(q)
        for _ in range(q_size):
            ci, cj, cnt = q.pop(0)

            if ci == 0 or ci == r-1 or cj == 0 or cj == c-1:
                return cnt + 1

            for k in range(4):
                ni, nj = ci + di[k], cj + dj[k]
                if 0 <= ni < r and 0 <= nj < c and not visited[ni][nj] and arr[ni][nj] == '.':
                    visited[ni][nj] = True
                    q.append((ni, nj, cnt+1)) 

    return 'IMPOSSIBLE'
            
ji = 0
jj = 0
fire = []
for i in range(r):
    for j in range(c):
        if arr[i][j] == 'J':
            ji = i
            jj = j
        elif arr[i][j] == 'F':
            fire.append((i, j))

print(escape(fire))

 

해결과정

불이 도달하기 전에 지훈이를 미로밖으로 탈출시켜야하는 문제.

문제를 보고 bfs로 풀기로 했지만, 불과 지훈이의 이동을 한턴씩 구현하는 것이 어려웠다.

첫 풀이는 (지훈이동 > 불이동 > 생존확인) 을 반복하면서 카운트를 해줬는데,

턴제 개념없이 구현해서 불이 생각보다 빨리 퍼지는 오류를 범했다.

불과 지훈이의 위치 정보를 각각의 큐에 저장하고, 매 턴마다 현재 큐에 있는 위치만큼만 이동하도록 제한( size = len(q) )하여 불과 지훈이가 동시에 한 칸씩 이동하도록 구현할 수 있었다.

 

+ python 문법

fire리스트를 bfs의 q에 추가할 때, 언패킹이 필요했다.

for 문으로 순회하면서 추가하는 방법도 있었지만 한줄로 끝내고 싶었던 와중에 extend() 는 리스트 끝에 가장 바깥쪽 iterable의 모든 항목을 넣는다는 정보를 습득하여 활용했다.

 

참고

https://m.blog.naver.com/wideeyed/221541104629