4179: 불!

문제 링크

4179: 불!

구현 방식

• 고려해야할 코너 케이스가 몇 가지 있었다
  • 1) 지훈이가 1초만에 통과할 수 있는 경우
  • 2) 처음에 지훈이와 불은 여러 군데 존재할 수 있다
• 도착점은 따로 ex(set)에 넣어서 처리해주었다
• bfs를 두 번 탐색해서 해결해주었다
  • 먼저, 불이 번지는 경우를 bfs로 처리해주고 결과값을 visit_f에 저장해주었다
  • 완성된 visit_f를 기준으로 지훈이의 탈출 과정을 처리해주었다
    • visit_f[nx][ny] == -1(불이 번지지 않은 위치)이거나 visit_f[nx][ny] > visit_j[x][y]+1(불보다 지훈이가 먼저 도달함)인 경우에 노드를 queue에 추가해주었다

코드

import sys
from collections import deque

dx = (0, 0, -1, 1)
dy = (-1, 1, 0, 0)

R, C = map(int, sys.stdin.readline()[:-1].split())

board = []; queue_f = deque([]); queue_j = deque([]); ex = set()
visit_f = [[-1]*C for r in range(R)]; visit_j = [[-1]*C for r in range(R)]
for r in range(R):
    tmp = list(sys.stdin.readline()[:-1])
    for c in range(C):
        if tmp[c] == 'J': queue_j.append((r, c)); visit_j[r][c] = 0
        elif tmp[c] == 'F': queue_f.append((r, c)); visit_f[r][c] = 0
        elif tmp[c] == '.' and (c == 0 or c == C-1 or r == 0 or r == R-1): ex.add((r, c))
    board.append(tmp)

tmp = list(queue_j)
for t in tmp:
    if t[0] == 0 or t[0] == R-1 or t[1] == 0 or t[1] == C-1: print(1); exit() #즉시 탈출할 수 있는 경우

while queue_f: #visit_f 완성
    x, y = queue_f.popleft()

    for i in range(4):
        nx = x + dx[i]; ny = y + dy[i]
        if 0 <= nx < R and 0 <= ny < C:
            if visit_f[nx][ny] == -1 and board[nx][ny] != '#':
                visit_f[nx][ny] = visit_f[x][y] + 1
                queue_f.append((nx, ny))

while queue_j: #지훈이 탈출 bfs
    x, y = queue_j.popleft()
    if (x, y) in ex:
        print(visit_j[x][y]+1); exit()
    
    for i in range(4):
        nx = x + dx[i]; ny = y + dy[i]
        if 0 <= nx < R and 0 <= ny < C:
            if visit_j[nx][ny] == -1 and board[nx][ny] == '.':
                if visit_f[nx][ny] == -1 or visit_f[nx][ny] > visit_j[x][y]+1:
                    visit_j[nx][ny] = visit_j[x][y] + 1
                    queue_j.append((nx, ny))

print("IMPOSSIBLE")