[Python] 백준 4179 불!

불!

처음 든 생각

• 최단거리니까 bfs + 지훈이도 탐색을 돌고 불도 돌리자
• 그런데 어떻게...?

처음 작성했을 때 불과 지훈이를 동시에 돌려서 문제 해결이 되지 않았다
둘 다 돌리는 건 맞지만 불이 먼저 확산되고, 지훈이가 움직일 수 있는지를 체크하는 게 중요할 듯


불 먼저 구현 + 지훈이 구현 했다

from collections import deque
import sys
sys.setrecursionlimit(1000)
R,C = map(int, input().split())
graph = []

for i in range(C):
    a = list((input().rstrip()))
    graph.append(a)

dx = [-1,1,0,0]
dy = [0,0,-1,1]

queue = deque()

fire = [[-1] * C for _ in range(R)]

for i in range(R):
    for j in range(C):
        if graph[i][j] == "F": # 불 초기 위치
            queue.append((i,j))
            fire[i][j] = 0
            
def bfs_fire():

    while queue:
        x, y = queue.popleft()

        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

			# 벽이 아닌 (좌표를 넘어가지 않고, #도 아닌), 불이 닿지 않은 곳이면
            if 0 <= nx < R and 0 <= ny < C and graph[nx][ny] != '#' and fire[nx][ny] == -1:
                fire[nx][ny] = fire[x][y] + 1
                queue.append((nx,ny))



bfs_fire()

print(fire)


# 4 4
# ####
# #JF#
# #..#
# #..#

• 위에 설명했듯 처음에는 불 좌표만 넣었는데, 그렇게 되면 언제 퍼진 불인지 몰라 지훈이가 어디로 나가야 할 지 모름 그래서 언제 퍼진지 표현하기 위해 +1로 변경했다

이제 지훈이 구현

틀린 풀이

from collections import deque
import sys
sys.setrecursionlimit(1000)
R,C = map(int, input().split())
graph = []

for i in range(C):
    a = list((input().rstrip()))
    graph.append(a)

dx = [-1,1,0,0]
dy = [0,0,-1,1]

fire = []

queue = deque()
queue2 = deque()

fire = [[-1] * C for _ in range(R)]
jihoon = [[-1] * C for _ in range(R)]

for i in range(R):
    for j in range(C):
        if graph[i][j] == "F":
            queue.append((i,j))
            fire[i][j] = 0
        if graph[i][j] == "J":
            queue2.append((i,j))
            jihoon[i][j] = 0
def bfs_fire():
    while queue:
        x, y = queue.popleft()

        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

            if 0 <= nx < R and 0 <= ny < C and graph[nx][ny] != '#' and fire[nx][ny] == -1:
                fire[nx][ny] = fire[x][y] + 1
                queue.append((nx,ny))

def bfs_jihoon():
    while queue2:
        x, y = queue2.popleft()

        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if not (0 <= nx < R and 0 <= ny < C):
                return jihoon[x][y] + 1
            if jihoon[nx][ny] == -1 and graph[nx][ny] != "#":
                if fire[nx][ny] == -1 or fire[nx][ny] > jihoon[nx][ny] + 1:
                    jihoon[nx][ny] = jihoon[x][y] + 1
                    queue2.append((nx,ny))
    return "IMPOSSIBLE"


bfs_fire()

result = bfs_jihoon()
print(result)


# 4 4
# ####
# #JF#
# #..#
# #..#

왜 틀렸을까 했는데 알고보니 지훈이가 탈출하는 조건이 잘못되었다...

최종

from collections import deque
import sys
sys.setrecursionlimit(1000)

R, C = map(int, input().split())
graph = []

for i in range(R):
    a = list(input().rstrip())
    graph.append(a)

dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

fire = deque()
queue2 = deque()

fire_time = [[-1] * C for _ in range(R)]
jihoon_time = [[-1] * C for _ in range(R)]

for i in range(R):
    for j in range(C):
        if graph[i][j] == "F":
            fire.append((i, j))
            fire_time[i][j] = 0
        elif graph[i][j] == "J":
            queue2.append((i, j))
            jihoon_time[i][j] = 0

def bfs_fire():
    while fire:
        x, y = fire.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < R and 0 <= ny < C and graph[nx][ny] != '#' and fire_time[nx][ny] == -1:
                fire_time[nx][ny] = fire_time[x][y] + 1
                fire.append((nx, ny))

def bfs_jihoon():
    while queue2:
        x, y = queue2.popleft()

        if x == 0 or y == 0 or x == R - 1 or y == C - 1:
            return jihoon_time[x][y] + 1

        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

            if 0 <= nx < R and 0 <= ny < C:
                if jihoon_time[nx][ny] == -1 and graph[nx][ny] != "#":
                    if fire_time[nx][ny] == -1 or fire_time[nx][ny] > jihoon_time[x][y] + 1:
                        jihoon_time[nx][ny] = jihoon_time[x][y] + 1
                        queue2.append((nx, ny))

    return "IMPOSSIBLE"

bfs_fire()
result = bfs_jihoon()
print(result)