해설
다른 사람들은 불을 먼저 bfs돌려서 번질 수 있는 경우의 수를 싹 봤다고 했는데 나는 동시에 돌렸다. 지훈이가 움직이는 경우인지, 불이 움직이는 경우인지 좌표와 함께 case 값(J / F)을 넣어줌으로써 처리해줬다.
그리고 지훈이가 그래프의 가장자리에 있을 때 (& 현재 탈출가능한 상태일때 -> graph[x][y]가 숫자일때) graph[x][y] + 1을 리턴해주고 그 외의 경우에는 IMPOSSIBLE을 리턴했다.
메모리초과
메모리초과가 가장 먼저 났는데 이건 큐에 불필요한 (이미 방문하여 방문할 필요가 없는) 좌표값이 들어가서였다.
-> 이동할 좌표가 .이어야 유효한 장소다. (방문 배열을 따로 두지 않고 그때그때 그래프를 보면서 방문했는지의 여부를 판단했다)
틀렸습니다의 향연
-
불은 계속해서 전파가 발생하며 벽을 제외하고 모든 곳으로 이동할 수 있다. 따라서 "#"이 아닌 경우 전파가 가능하다. 불이 있는 곳은 애초에 움직일 수 없는 곳이므로 불의 좌표만
q에 넣어두고 불이 번진 곳은 전부 벽(#)과 동일하게 처리해줬다.
지훈이는 상하좌우로 움직이면서 현재 몇분째인지를 숫자로 계산해줬다. 여기에서 주의해줄 점은 지훈이를 먼저 이동시키고 그 후에 불을 전파시켰는데, 지훈이가 움직일 수 있는 좌표로q에 잘 넣어뒀는데, 후에 그 자리에 불이 전파된 경우 그 자리는 움직이면 안되는 자리다!!! 즉,q에서 값을 꺼내서 계산해줄 때 지훈이가 움직이는 순간 해당 좌표값이#인지 (불이 전파되어 움직일 수 있는 경우X) 체크를 해줘야한다. -
또 주의할 점은 J의 값만 1개로 주어진다는 것이다. 즉, 불은 여러 곳에 위치할 수 있다. 혹시 불이 없는 장소도 있을까 싶어 배열로 입력받은 뒤 배열의 길이가 0일때도 예외처리해줬다.
하다하다 구글링을 통해 테스트케이스들을 찾아서 예외처리를 할 수 있었다. 함께 첨부해둬야지.
TC 1 : 4
5 5
....F
...J#
....#
....#
...#.
TC 2 : IMPOSSIBLE
3 3
F.F
.J.
F.F
TC 3 : IMPOSSIBLE
5 5
#####
#...#
#.J.#
#...#
#####최종 코드
from sys import stdin
from collections import deque
input = stdin.readline
R, C = map(int, input().split())
graph = []
pos_j = [] # 지훈 위치
pos_f = [] # 불 위치
for i in range(R):
tmp = list(input())
for j in range(C):
if tmp[j] == "J":
pos_j.append((i, j))
elif tmp[j] == "F":
pos_f.append((i, j))
graph.append(tmp)
q = deque()
q.append((pos_j[0][0], pos_j[0][1], "J")) # 지훈이가 먼저 이동
graph[pos_j[0][0]][pos_j[0][1]] = 0
if len(pos_f) != 0:
for (r, c) in pos_f:
q.append((r, c, "F"))
graph[r][c] = "#"
def bfs():
dx = [-1, 1, 0, 0] # 상하좌우
dy = [0, 0, -1, 1]
while q:
x, y, case = q.popleft()
if case == "J" and (x == 0 or y == 0 or x == R - 1 or y == C - 1): # 탈출가능
if graph[x][y] == "#":
continue
return graph[x][y] + 1
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] != "#" and case == "F":
graph[nx][ny] = "#"
q.append((nx, ny, "F"))
elif graph[nx][ny] == "." and case == "J" and graph[x][y] != "#":
graph[nx][ny] = graph[x][y] + 1
q.append((nx, ny, "J"))
return "IMPOSSIBLE"
print(bfs())눈물만 흘렀던 백준화면^^
