get_exit()로 시간의 벽의 출구의 방향 및 좌표를 얻고, 출구가 있는 면엔 [0,1,1,...], 나머지 면엔 [1,1,...]를 M번째 행으로 추가하기warp(nr,nc,side)로 경계 이탈 시 면 이동 및 좌표 변환하기, 경계 이탈하지 않으면 그대로 (nr,nc,side) 반환하기(M번째 행 추가한 맵의 인덱스 체크 주의)- 이상현상이 언제 해당 칸으로 확산되는지를 미리 계산해서 맵에 기록해두기
- 미지의 공간 BFS: 시작점 (s_start_r,s_start_c)에서 space_maps를 따라 확장하되, 해당 칸의 이상현상 확산시간 num에 대해
T+turn+1 < num일 때만 지나갈 수 있도록 구현하기(타임머신이 지나가기 직전에 이상현상이 먼저 확산됨 주의!)
from collections import deque
N, M, F = map(int, input().split())
space_maps = []
# 미지의 공간 평면도
for i in range(N):
line = list(map(int, input().split()))
for j in range(N):
# 탈출구 -1로 표기 변경 (맵에 이상현상의 확산 시간을 양수로 표기할 것이므로)
if line[j] == 4:
line[j] = -1
space_maps.append(line)
# 시간의 벽의 각 면의 2차원 맵
time_east = []
time_west = []
time_south = []
time_north = []
time_top = []
TOP, NORTH, EAST, SOUTH, WEST = 0, 1, 2, 3, 4
start_r, start_c = -1, -1
for j in range(M):
line = list(map(int, input().split()))
time_east.append(line)
for j in range(M):
line = list(map(int, input().split()))
time_west.append(line)
for j in range(M):
line = list(map(int, input().split()))
time_south.append(line)
for j in range(M):
line = list(map(int, input().split()))
time_north.append(line)
for j in range(M):
line = list(map(int, input().split()))
for l in range(M):
# 타임머신 시작 좌표 저장
if line[l] == 2:
start_r, start_c = j, l
time_top.append(line)
time_maps = []
time_maps.extend([time_top, time_north, time_east, time_south, time_west])
# 이상 현상 저장 리스트
strange = []
for i in range(F):
line = list(map(int, input().split()))
strange.append(line)
# 시간의 벽의 단 한칸의 출구의 방향 및 좌표 구하기
def get_exit():
for i in range(N):
for j in range(N):
if space_maps[i][j] == 3:
# 북쪽에 출구
for k in range(M):
if 0 <= i - 1 < N and 0 <= j + k < N and space_maps[i - 1][j + k] == 0:
return 1, M - 1 - k, i - 1, j + k
# 서쪽에 출구
for k in range(M):
if 0 <= i + k < N and 0 <= j - 1 < N and space_maps[i + k][j - 1] == 0:
return 4, k, i + k, j - 1
# 동쪽에 출구
for k in range(M):
if 0 <= i + k < N and 0 <= j + M < N and space_maps[i + k][j + M] == 0:
return 2, M - 1 - k, i + k, j + M
# 남쪽에 출구
for k in range(M):
if 0 <= i + M < N and 0 <= j + k < N and space_maps[i + M][j + k] == 0:
return 3, k, i + M, j + k
# 시간의 벽 탈출한 후 시작점 좌표
s_start_r, s_start_c = -1, -1
exit_dir, k, s_start_r, s_start_c = get_exit()
others = [] # 출구를 가지지 않는 면들
# 시간의 벽의 출구(0)와 장애물인 곳(1)을 시간의 벽 맵에 표시해주기
line = []
for i in range(M):
if i == k:
line.append(0)
else:
line.append(1)
time_maps[exit_dir].append(line)
# 시간의 벽 출구가 없는 면들에는 1로 채워진 리스트 추가해주기(BFS에서 아래로 더 나아갈 수 없도록)
for i in range(1, 5):
if i == exit_dir:
continue
line = []
for j in range(M):
line.append(1)
time_maps[i].append(line)
# 0: top, 1: north, 2: east, 3: south, 4: west
dx = [0, 0, 1, -1] # 동, 서, 남, 북 순
dy = [1, -1, 0, 0]
# 시간의 벽에서의 탈출 경로 탐색 BFS
def bfs_time_space():
visited = [set(), set(), set(), set(), set()]
q = deque()
q.append((start_r, start_c, 0, 0))
visited[0].add((start_r, start_c))
min_turn = -1
# 시간의 벽의 다른 면으로 좌표 변환 처리 함수
def warp(nr, nc, side):
# warp 해당 사항 없다면 기존 그대로 리턴
if side == 0 and 0 <= nr < M and 0 <= nc < M:
return nr, nc, side
elif 1 <= side <= 4 and 0 <= nr <= M and 0 <= nc < M:
return nr, nc, side
if side == TOP:
if nr < 0:
return 0, M - 1 - nc, NORTH
elif nr > M - 1:
return 0, nc, SOUTH
elif nc < 0:
return 0, nr, WEST
elif nc > M - 1:
return 0, M - 1 - nr, EAST
elif side == NORTH:
if nr < 0:
return 0, M - 1 - nc, TOP
elif nc < 0:
return nr, M - 1, EAST
elif nc > M - 1:
return nr, 0, WEST
elif side == EAST:
if nr < 0:
return M - 1 - nc, M - 1, TOP
elif nc < 0:
return nr, M - 1, SOUTH
elif nc > M - 1:
return nr, 0, NORTH
elif side == SOUTH:
if nr < 0:
return M - 1, nc, TOP
elif nc < 0:
return nr, M - 1, WEST
elif nc > M - 1:
return nr, 0, EAST
elif side == WEST:
if nr < 0:
return nc, 0, TOP
elif nc < 0:
return nr, M - 1, NORTH
elif nc > M - 1:
return nr, 0, SOUTH
while q:
r, c, side, turn = q.popleft()
if r == M:
min_turn = turn
break
for i in range(4):
nr, nc = r + dx[i], c + dy[i]
# 동,서,남,북 면에 있을 때 nr이 M 초과 시 맵 밖이므로 패스
if 1 <= side <= 4 and nr > M:
continue
# 좌표 warp
n_r, n_c, new_side = warp(nr, nc, side)
if (n_r, n_c) not in visited[new_side] and time_maps[new_side][n_r][n_c] == 0:
q.append((n_r, n_c, new_side, turn + 1))
visited[new_side].add((n_r, n_c))
# 탈출까지 최소 소요 시간 리턴
return min_turn
T = bfs_time_space()
# 시간의 벽을 탈출한 후 미지의 공간의 탈출 경로 탐색 BFS
def bfs_space():
q = deque()
visited = set()
q.append((s_start_r, s_start_c, 0))
visited.add((s_start_r, s_start_c))
time = -1
while q:
#print(q)
r, c, turn = q.popleft()
# 탈출구에 도착했다면
if space_maps[r][c] == -1:
time = turn
break
for i in range(4):
nr, nc = r + dx[i], c + dy[i]
if 0 <= nr < N and 0 <= nc < N and space_maps[nr][nc] != 1 and (nr, nc) not in visited:
num = space_maps[nr][nc]
# 그냥 빈공간이거나 탈출구라면 지나가기
if num == 0 or num == -1:
q.append((nr, nc, turn + 1))
visited.add((nr, nc))
# 미래에 이상현상 퍼질 공간이라면, 내가 지나갈 시간보다 퍼지는 시간이 이후라면
elif T + turn + 1 < num:
q.append((nr, nc, turn + 1))
visited.add((nr, nc))
return time
# 맵에 이상 현상 시작지점 표시
for s in strange:
r, c, d, v = s[0], s[1], s[2], s[3]
space_maps[r][c] = 1
# 맵에 각 이상현상이 확산되는 시간을 표기
for s in strange:
r, c, d, v = s[0], s[1], s[2], s[3]
nr, nc = r + dx[d], c + dy[d]
turn = 1
# 항상 다음 좌표 생성 시 맵 내부인지 인덱스 체크 꼭 하기!
while 0 <= nr < N and 0 <= nc < N and space_maps[nr][nc] == 0:
space_maps[nr][nc] = v * turn
turn += 1
nr, nc = nr + dx[d], nc + dy[d]
# 시간의 벽을 탈출할 수 없다면
if T == -1:
print(-1)
# 아래 시간의 벽 탈출구에 이미 이상현상이 퍼졌다면 실패
elif space_maps[s_start_r][s_start_c] != 0 and T >= space_maps[s_start_r][s_start_c]:
print(-1)
else:
time = bfs_space()
if time == -1:
print(-1)
else:
print(T + time)
