[백준] 4179번 불! ★

💡문제접근

• 전체적인 로직을 이해하는데에 성공했다. 불의 이동과 지훈이의 이동 둘 다 고려를 해줘야한다는 것을 파악했지만 머릿속에 있는 로직을 코드로 옮기는 구현의 과정에서 정말 오랜 시간이 걸렸던 문제였다. 관련 문제로는 [[백준] 5427번 불]이 있다.

💡코드(메모리 : 71596KB, 시간 : 1592ms)

import sys
input = sys.stdin.readline
from collections import deque

def BFS():
    while fire_queue:
        x, y = fire_queue.popleft()

        dx = [-1, 0, 1, 0]
        dy = [0, 1, 0, -1]
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            # 불이 영역 밖으로 번지지는 않으므로
            if nx < 0 or nx >= R  or ny < 0 or ny >= C:
                continue
            # 불이 벽에는 번지지 않았거나 이미 번진 경우라면?
            if graph[nx][ny] == '#' or fire_visited[nx][ny]:
                continue
            
            fire_visited[nx][ny] = fire_visited[x][y] + 1
            fire_queue.append((nx, ny))

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

        dx = [-1, 0, 1, 0]
        dy = [0, 1, 0, -1]
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if nx < 0 or nx >= R or ny < 0 or ny >= C:
                return visited[x][y]
				
            # 만약 해당 좌표가 이동할 수 없는 벽이라면?
            if graph[nx][ny] == '#':
                continue
            # 이미 거쳐온 좌표라면 다시 갈 필요가 없기 때문에
            if visited[nx][ny]:
                continue
            # 불의 이동이 나타난 좌표이지만 만약 사람이 불의 번짐 속도와 동일하면?
            if fire_visited[nx][ny] and visited[x][y] + 1 >= fire_visited[nx][ny]:
                continue
		
            visited[nx][ny] = visited[x][y] + 1
            queue.append((nx, ny))
    return "IMPOSSIBLE"

R, C = map(int, input().strip().split())
graph = []
for _ in range(R):
    graph.append(list(input().strip()))

queue = deque()
fire_queue = deque()
fire_visited = [[0] * C for _ in range(R)]
visited = [[0] * C for _ in range(R)]
for i in range(R):
    for j in range(C):
        if graph[i][j] == 'J':
            queue.append((i, j))
            visited[i][j] = 1
        elif graph[i][j] == 'F':
            fire_queue.append((i, j))
            fire_visited[i][j] = 1
print(BFS())

💡소요시간 : 2h