import sys
from collections import deque, defaultdict
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
r, c = map(int, sys.stdin.readline().rstrip().split())
graph = [list(sys.stdin.readline().rstrip()) for _ in range(r)]
graph_cnt = [[9999] * c for _ in range(r)]
start_pos = deque()
fire_pos = deque()
for i in range(r):
for j in range(c):
if graph[i][j] == 'J':
start_pos.append((i, j))
elif graph[i][j] == 'F':
graph_cnt[i][j] = 0
fire_pos.append((i, j))
# fire check
while fire_pos:
x, y = fire_pos.popleft()
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if 0 <= nx < r and 0 <= ny < c:
if graph[nx][ny] == '#':
continue
if graph_cnt[nx][ny] > graph_cnt[x][y] + 1:
graph_cnt[nx][ny] = graph_cnt[x][y] + 1
fire_pos.append((nx, ny))
result = defaultdict(int)
for i in range(c):
if graph[0][i] != '#' and graph_cnt[0][i] != 9999:
result[(0, i)] = graph_cnt[0][i]
if graph[r-1][i] != '#' and graph_cnt[r-1][i] != 9999:
result[(r-1, i)] = graph_cnt[r-1][i]
for i in range(r):
if graph[i][0] != '#' and graph_cnt[i][0] != 9999:
result[(i, 0)] = graph_cnt[i][0]
if graph[i][c-1] != '#' and graph_cnt[i][c-1] != 9999:
result[(i, c-1)] = graph_cnt[i][c-1]
for i in range(r):
for j in range(c):
if graph_cnt[i][j] != 9999:
graph_cnt[i][j] = 9999
graph_cnt[start_pos[0][0]][start_pos[0][1]] = 0
while start_pos:
x, y = start_pos.popleft()
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if 0 <= nx < r and 0 <= ny < c:
if graph[nx][ny] == '#':
continue
if graph_cnt[nx][ny] > graph_cnt[x][y] + 1:
graph_cnt[nx][ny] = graph_cnt[x][y] + 1
start_pos.append((nx, ny))
if not result:
ans = []
no_fire_result = defaultdict(int)
for i in range(c):
if graph[0][i] != '#' and graph_cnt[0][i] != 9999:
no_fire_result[(0, i)] = graph_cnt[0][i]
if graph[r - 1][i] != '#' and graph_cnt[r - 1][i] != 9999:
no_fire_result[(r - 1, i)] = graph_cnt[r - 1][i]
for i in range(r):
if graph[i][0] != '#' and graph_cnt[i][0] != 9999:
no_fire_result[(i, 0)] = graph_cnt[i][0]
if graph[i][c - 1] != '#' and graph_cnt[i][c - 1] != 9999:
no_fire_result[(i, c - 1)] = graph_cnt[i][c - 1]
for pos in no_fire_result:
ans.append(no_fire_result[pos]+1)
if not ans:
print('IMPOSSIBLE')
else:
print(sorted(ans)[0])
else:
ans = []
for pos in result:
x, y = pos
fire = result[pos]
j = graph_cnt[x][y]
if j < fire:
ans.append(j + 1)
if not ans:
print('IMPOSSIBLE')
else:
print(sorted(ans)[0])
일단 답만 맞아보려고 급하게 코드를 작성했음. 시간초과 나지 않는 코드 완성되면 수정 예정
import sys
from collections import deque
def fire_move():
while fire_q:
x, y = fire_q.popleft()
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if 0 <= nx < r and 0 <= ny < c:
if graph[nx][ny] == '#':
continue
if fire[nx][ny] > fire[x][y] + 1 and not fire_v[nx][ny]:
fire_v[nx][ny] = True
fire[nx][ny] = fire[x][y] + 1
fire_q.append((nx, ny))
def jay_move():
while jay_q:
x, y = jay_q.popleft()
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if not 0 <= nx < r or not 0 <= ny < c:
print(jay[x][y] + 1)
return
if 0 <= nx < r and 0 <= ny < c:
if graph[nx][ny] == '#' or graph[nx][ny] == 'F':
continue
if fire[nx][ny] > jay[x][y] + 1 and not jay_v[nx][ny]:
jay_v[nx][ny] = True
jay[nx][ny] = jay[x][y] + 1
jay_q.append((nx, ny))
print('IMPOSSIBLE')
return
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
INF = float('inf')
r, c = map(int, sys.stdin.readline().rstrip().split())
graph = [list(sys.stdin.readline().rstrip()) for _ in range(r)]
fire = [[INF] * c for _ in range(r)]
jay = [[INF] * c for _ in range(r)]
fire_v = [[False] * c for _ in range(r)]
jay_v = [[False] * c for _ in range(r)]
fire_q = deque()
jay_q = deque()
for i in range(r):
for j in range(c):
if graph[i][j] == 'J':
jay_q.append((i, j))
jay[i][j] = 0
elif graph[i][j] == 'F':
fire_q.append((i, j))
fire[i][j] = 0
fire_move()
jay_move()
방문 여부를 저장하는 2차원 배열을 선언해야 메모리 초과가 발생하지 않는다.