4179. 불!

문제 링크

불!

문제 코드

from collections import deque

num_list = list(map(int,input().split()))

row = num_list[0]
col = num_list[1]

maze = [[0 for c in range(col)]for r in range(row)]
fire = [[float('INF') for c in range(col)]for r in range(row)]
visited = [[0 for c in range(col)]for r in range(row)]

fire_list = deque()
for i in range(row):
    tmp_maze = input()

    for j in range(col):
        maze[i][j] = tmp_maze[j]

        if tmp_maze[j]=='J':
            jihun = [i,j]
        if tmp_maze[j]=='F':
            fire[i][j] = 0
            fire_list.append([i,j])
        if tmp_maze[j]=='#':
            fire[i][j] = -1

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

while len(fire_list) >0:
    now_fire = fire_list.popleft()
    x = now_fire[0]
    y = now_fire[1]
    count = fire[x][y]

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

        if 0<=next_x<row and 0<=next_y<col and fire[next_x][next_y] == float('INF'):
            fire_list.append([next_x,next_y])
            fire[next_x][next_y] = count+1

#print(fire)

que = deque()

que.append([jihun,1])
visited[jihun[0]][jihun[1]] = 1

min_count = float('INF')
while len(que)>0:
    tmp = que.popleft()
    x,y = tmp[0]
    count = tmp[1]
    if x == 0 or x == row-1 or y ==0 or y == col-1:
        min_count = count
        break

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

        if 0<=next_x<row and 0<=next_y<col and visited[next_x][next_y] == 0 and fire[next_x][next_y] > count and maze[next_x][next_y]=='.':
            visited[next_x][next_y] = 1
            que.append([[next_x,next_y],count+1])

if min_count == float('INF'):
    print('IMPOSSIBLE')

else:
    print(min_count)

문제 풀이

• 불을 먼저 퍼트려서 불이 지나가는 위치의 시간대를 먼저 기록해 두었다.
• 지훈이가 움직일때는 불이 지나간 시간대보다 먼저 지나가야 한다.
• 처음에는 fire를 0으로 두고 했는데, 불이 아예 막히는 경우의 수도 고려해야한다. 따라서 inf로 초기값을 설정

추가 예시

4 4

####
JF.#
#..#
#..#

answer : 1

4 4
###F
#J.#
#..#
#..#
answer :3

4 6

######
......
#.J###
#F####    

answer : 5