1. 아이디어

• 먼저, 아래 코드로 구현한 이 문제의 시간 복잡도는 다음과 같다.

  $O(RC) \\$
  $\ RC = 배열의\;크기 \quad \quad \quad (1 ≤ R, C ≤ 100)\\$

• 미로를 탈출할 수 있는 가장 빠른 탈출시간을 구하기 위해 bfs 알고리즘을 이용하였다.

• 불과, 준수가 동시에 이동하므로 bfs알고리즘을 돌리기 전에 불과, 준수의 좌표를 deque에 넣어 준다

• deque에 들어간 좌표가 불과 준수임을 확인해 주기 위해 아래의 코드와 같이 구분해 주었다.

        if a[i][j] == 'J':
            visit[i][j] = 1
            q.append((i, j, 'J'))
        if a[i][j] == 'F':
            visit[i][j] = 1
            q.appendleft((i, j, 'F'))

• 불의 좌표를 먼저 넣어주어야 하는데, 그 이유는 아래의 경우처럼 준수가 먼저 들어갈 경우 오답이 나올 수 있기 때문이다.

• FIFO에 따라 아래 그림과 같이 불이 먼저 확산 되고 준수가 이동하게 된다.
  

2. 코드

from collections import deque
dx = [0, 0, -1, 1]
dy = [-1, 1, 0, 0]


def bfs(q):

    while q:
        x, y, s = q.popleft()
        for i in range(4):
            nx, ny = x+dx[i], y+dy[i]
            if 0 <= nx < n and 0 <= ny < m:
                if not visit[nx][ny] and a[nx][ny] == '.':
                    q.append((nx, ny, s))
                    visit[nx][ny] = visit[x][y] + 1
            else:
                if s == 'J':
                    return visit[x][y]


n, m = map(int, input().split())
a = [list(input()) for _ in range(n)]
visit = [[0]*m for _ in range(n)]
q = deque()

for i in range(n):
    for j in range(m):
        if a[i][j] == 'J':
            visit[i][j] = 1
            q.append((i, j, 'J'))
        if a[i][j] == 'F':
            visit[i][j] = 1
            q.appendleft((i, j, 'F'))

ans = bfs(q)
if ans:
    print(ans)
else:
    print('IMPOSSIBLE')

문제 출처

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