문제
미지의 공간 탈출
당신은 시간 여행자입니다. 시간 여행 도중 타임머신의 오작동으로 인해 크기 의 미지의 공간에 갇히게 되었습니다. 당신은 타임머신을 타고 이 공간에서 탈출해야 합니다. 탈출하기 위해, 타임머신의 기능을 활용하여 이 공간의 지리 정보를 파악했습니다.
이 공간은 한 변의 길이가 인 2차원 평면이며, 그 사이 어딘가에는 한 변의 길이가 인 정육면체 형태의 시간의 벽이 세워져 있습니다.
타임머신의 스캔 기능을 통해 다음의 정보를 얻을 수 있었습니다:
- 미지의 공간의 평면도: 위에서 내려다본 전체 맵입니다.
- 시간의 벽의 단면도: 시간의 벽의 윗면과 동서남북 네 면의 단면도입니다.
이 평면도와 단면도는 빈 공간과 장애물로 구성되어 있으며, 각각 0과 1로 표현됩니다. 당신의 타임머신은 빈 공간만 이동할 수 있으며, 장애물 위치로는 이동할 수 없습니다.
당신의 타임머신은 시간의 벽의 윗면 어딘가에 위치하며, 시간의 벽의 윗면 단면도에서는 타임머신의 위치 2가 추가로 표시됩니다. 마찬가지로 미지의 공간의 평면도에서는 시간의 벽의 위치 3과 탈출구 4가 추가로 표시됩니다. 탈출구는 시간의 벽 외부에 있는 미지의 공간의 바닥에 위치합니다.
시간의 벽과 맞닿은 미지의 공간의 바닥은 기본적으로 장애물들로 둘러 쌓여있습니다. 그러나 단 한 칸만 빈 공간으로 뚫려 있기 때문에 시간의 벽에서 미지의 공간의 바닥으로 이어질 수 있는 출구는 하나입니다.
또한, 미지의 공간의 바닥에는 총 개의 시간 이상 현상이 존재합니다. 각 시간 이상 현상은 바닥의 빈 공간 에서 시작하여 매 의 배수 턴마다 방향 로 한 칸씩 확산되며, 확산된 이후에도 기존 위치의 시간 이상 현상은 사라지지 않고 남아 있습니다. 시간 이상 현상은 장애물과 탈출구가 없는 빈 공간으로만 확산되며, 더 이상 확산할 수 없을 경우 멈춥니다. 모든 시간 이상 현상은 서로 독립적이며 동시에 확산됩니다. 방향 는 동(0), 서(1), 남(2), 북(3)으로 표시됩니다.
당신의 타임머신은 매 턴마다 상하좌우로 한 칸씩 이동할 수 있으며, 장애물과 시간 이상 현상을 피해 탈출구까지 도달해야 합니다. 타임머신이 시작점에서 탈출구까지 이동하는 데 필요한 최소 시간(턴 수)을 출력하는 프로그램을 작성해야 합니다. 만약 탈출할 수 없다면 -1을 출력합니다. 시간 이상 현상이 확산된 직후 타임머신이 이동하기 때문에, 타임머신은 시간 이상 현상이 확산되는 곳으로 이동할 수 없음에 유의합니다.
입력
첫 번째 줄에 미지의 공간의 한 변의 길이 , 시간의 벽 한 변의 길이 , 시간 이상 현상의 개수 가 공백을 사이에 두고 차례로 주어집니다.
다음 개의 줄에 걸쳐 미지의 공간의 평면도가 주어집니다.
다음 줄부터 시간의 벽의 동, 서, 남, 북, 윗면의 단면도가 각각 줄에 걸쳐 차례로 주어집니다.
그 다음 줄에 걸쳐 각 시간 이상 현상의 초기 위치 , 와 확산방향 , 확산상수 가 공백을 사이에 두고 차례로 주어집니다.
출력
타임머신이 시작점에서 탈출구까지 이동하는 데 필요한 최소 시간(턴 수)을 출력하세요.
만약 탈출할 수 없다면 -1을 출력합니다.
예제 1
8 3 2
4 0 0 0 0 0 0 0
0 1 1 1 1 1 0 0
0 1 3 3 3 1 0 1
0 1 3 3 3 1 0 1
0 1 3 3 3 0 0 0
0 1 1 1 1 1 1 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 1 1
1 1 1
0 0 0
0 1 1
1 1 1
1 0 1
1 1 1
0 0 1
1 0 0
1 0 1
0 0 0
1 0 0
1 1 1
2 0 0
0 1 0
0 0 0
0 7 1 14
6 3 3 2
출력
28
미지의 공간은 <왼쪽 그림>처럼 생겼고, <오른쪽 그림> 최단거리로 나가려 합니다.
하지만 t=14일 때, <왼쪽 그림>처럼 시간 이동 현상 때문에 위로 갈 수 없다, 따라서 <오른쪽 그림> 처럼 28 이 정답입니다.
해설
주요포인트
- 3차원 "시간의 벽"을 어떻게 BFS 돌릴지 생각(측면 연결 방법)
- "시간이상현상"은 "미지의 공간"에서 시작
- "타임머신"은 "시간의 벽"에서 시작
- "탈출구"는 "미지의 공간"에만 있음
- "시간의 벽"탈출 시, "시간이상현상"이 막아서 못 나오는 경우
- "시간의 벽"의 출구는 오직 한 곳
- "이상현상"이 시간초에서 타임머신보다 선행되어야 함
=> 14초가 되었을 때, 이상현상이 먼저 움직여야 함
(BFS특성상 큐에 먼저 들어가버리면 알고리즘이 돌아가므로, 큐에 넣기전에 먼저 판별해야함⭐️)
필요지식
- 2차원 메트리스 돌리기
- 2차원 배열 hardcopy
개인해설
3차원 "시간의 벽"을 어떻게 구현하는지가 핵심입니다.
2차원으로 바꿔야겠다고 생각했고, 주사위 전개도처럼 펼쳐서 풀었습니다.
핵심
- 1) 인풋과 전개도 모양 달라서 남방향을 제외하고,(서,동,북) 전개도는 2차원 메트리스 돌리기 해야함
- 2) 시간의 벽 출구 매핑
- 3) 측면 이어주는거 해야함(어렵🔥)
1) 전개도 만들어서 시간의 벽 탈출하기
1-1) 2차원 매트리스 돌리기
전개도가 똑바로 전개되도록 (남방향)제외하고, (북,서,동) 돌리기
time_wall = [[5]*(3*m+2) for _ in range(3*m+2)]
for i in range(3*m+2):
time_wall[0][i] = 9
time_wall[3*m+1][i] = 9
time_wall[i][0] = 9
time_wall[i][3*m+1] = 9
# 동
c_mat = [0]*m
cc_mat = [[0]*m for _ in range(m)]
for i in range(m):
c_mat[i] = list(map(int, input().split()))
for i in range(m):
for j in range(m):
cc_mat[m-1-j][i] = c_mat[i][j]
for i in range(m):
for j in range(m):
time_wall[m+1+i][2*m+1+j] = cc_mat[i][j]
# 서
c_mat = [0]*m
cc_mat = [[0]*m for _ in range(m)]
for i in range(m): # 서
c_mat[i] = list(map(int, input().split()))
for i in range(m):
for j in range(m):
cc_mat[j][m-1-i] = c_mat[i][j]
for i in range(m):
for j in range(m):
time_wall[m+1+i][1+j] = cc_mat[i][j]
# 남
for i in range(m):
arr = list(map(int, input().split()))
for j in range(m):
time_wall[2*m+1+i][m+1+j] = arr[j]
# 북
c_mat = [0]*m
cc_mat = [[0]*m for _ in range(m)]
for i in range(m):
c_mat[i] = list(map(int, input().split()))
for i in range(m):
for j in range(m):
cc_mat[m-1-i][m-1-j] = c_mat[i][j]
for i in range(m):
for j in range(m):
time_wall[i+1][m+1+j] = cc_mat[i][j]
# 윗면
for i in range(m):
arr = list(map(int, input().split()))
for j in range(m):
time_wall[m+1+i][m+1+j] = arr[j]
2) 시간의 벽 출구 매핑
time_wall = [[5]*(3*m+2) for _ in range(3*m+2)]저는 이런식으로 만들었고 +2 로 패딩을 줘서 9로 벽을 막았습니다.
그리고 따로 맵을 만든만큼, 해당 출구 7을 매핑해주어야 했습니다.
빨강부분만 탈출 가능하기에
start_x, start_y는 좌상단부터 순차탐색을 하므로 주어진 2차원 매트리스에서 3(= 시간의 벽)을 찾았을 때
항상 시간의 벽의 최상단좌를 먼저 발견합니다. 그에 따라서 상대범위를 측청하여 <오른쪽 그림> 처럼 매핑했습니다.
# 2) 시간의 벽에다가 값으로 매핑하기
time_wall_mapping(time_exit[0]-start_x, time_exit[1]-start_y)
def time_wall_mapping(i ,j):
if i<0:
time_wall[0][m+1+j] = 7 #북
elif i>=m:
time_wall[3*m+1][m+1+j] = 7 #남
elif j<0:
time_wall[m+1+i][0] = 7 # 서
else:
time_wall[m+1+i][3*m+1] = 7 # 동
3) 측면 이어주기
이제 2차원으로 전개한 시간의 벽을 BFS 돌아서 탈출구(7)로 탈출해야함. -> 측면 간다면, side_mapping()으로 가서 측면이동 실행
이때 패딩전략과 2차원 매트리스에 대한 이해도가 문제에 도움이 될 것이다.
<왼쪽 그림>처럼 임의로 숫자를 배정해서 자기만의 스토리를 구사한다.
<오른쪽 그림>처럼 초록선을 기준으로 이동하는데
(m+1), (2*m)가 경계선이다. 나는 둘 다 +1이 붙는지 알고 틀렸었다.
디버깅 빠르게 하는 법
- 직접 해당 벽면들 숫자매칭해보며 값이 제대로 이동하는 지 확인하기
이유: 노가다 작업에서 휴먼에러 가장 많이 발생.
def time_bfs(i, j):
que = deque()
que.append((i,j,0))
visited = [[False]*(3*m+2) for _ in range(3*m+2)]
visited[i][j] = True
flag = 0
sec = -1
while que:
x, y, cnt = que.popleft()
for dx, dy in move:
px, py = x+dx, y+dy
if 0<=px<3*m+2 and 0<=py<3*m+2 and not visited[px][py]:
if time_wall[px][py] == 5: # 측면이동
visited[px][py] = True # 방문 처리
px, py = side_mapping(x, y) # 옆면으로
if not visited[px][py]:
if time_wall[px][py] == 0:
que.append((px, py, cnt+1))
visited[px][py] = True
elif time_wall[px][py] == 7: # 시간의 벽 탈출
flag = 1
sec = cnt # 시간초
break
elif time_wall[px][py] == 0:
que.append((px, py, cnt+1))
visited[px][py] = True
elif time_wall[px][py] == 7: # 시간의 벽 탈출
flag = 1
sec = cnt # 시간초
break
if flag == 1:
break
return sec
def side_mapping(x, y):
if x == m+1:
if y < m+1: # 1 -> 2
return y, x
elif y > 2*m: # 4 -> 3
return m+1-(y-(2*m)),2*m
elif x == 2*m:
if y < m+1: # 5 -> 6
return 2*m+y,m+1
elif y > 2*m: # 7 -> 8
return y, x
elif y == m+1:
if x < m+1: # 2 -> 1
return y, x
elif x > 2*m: # 6 -> 5
return 2*m, x-(2*m)
elif y == 2*m:
if x < m+1: # 3 -> 4
return m+1, 2*m+x
elif x > 2*m: # 8 -> 7
return y, x2) 미지의 공간 탈출구로 탈출하기
시간의 벽을 탈출할 수 있는지 체크한다.
1) 시간의 벽 탈출 실패: 못하면 flag=1
or
2) 이상현상이 탈출구 막음
이때 2차원 배열 지우는 지식 필요
1) idx를 저장했다가 한 번에 복사하는 방법 택함
# 3) 시간의 벽 탈출하기
result = -1 # 시간초
flag = 0
for i in range(3*m+2):
for j in range(3*m+2):
if time_wall[i][j] == 2: # 타임머신 장소
temp_sec = time_bfs(i, j)
if temp_sec == -1: # 장애물로 탈출 불가능
flag = 1
else:
result = temp_sec
# 4) 시간의 벽에서 나왔는데 이상현상이 막으면 탈출실패
delete_num = []
for idx, stop in enumerate(stop_spread):
r, c, d, v = stop
value = result//v # 움직인 거리
if value > 0: # 확산해야 한다면
for i in range(1, value+1):
px, py = r+(move[d][0]*i), c+(move[d][1]*i)
if 0<=px<n and 0<=py<n and mat[px][py]==0:
mat[px][py] = 1 # 장애물
else:
delete_num.append(idx) # 삭제
break # 탈출
stop_spread[idx] = (r+(move[d][0]*value), c+(move[d][1]*value), d, v) # x,y,d
temp = []
for idx in range(len(stop_spread)):
if idx not in delete_num:
temp.append(stop_spread[idx])
stop_spread = temp[:]
if flag == 1 or mat[time_exit[0]][time_exit[1]] == 1: # 시간의 벽 탈출못하면 or 이상현상이 막으면
print(result)
탈출구 BFS
def bfs(i, j, c):
que = deque()
que.append((i,j,c))
visited = [[False]*n for _ in range(n)]
visited[i][j] = True
g_cnt = c # 글로벌 시간초
while que:
# print("que", que)
x, y, cnt = que.popleft()
for dx, dy in move:
px, py = x+dx, y+dy
if 0<=px<n and 0<=py<n and not visited[px][py]:
if cnt+1 > g_cnt: # 다음초로 넘어갔다면
g_cnt += 1 # 시간초 증가
for idx, stop in enumerate(stop_spread):# 이상현상 발생
r, c, d, v = stop
if g_cnt%v == 0: # 움직일 차례면
mx, my = r+move[d][0], c+move[d][1]
if 0<=mx<n and 0<=my<n and mat[mx][my]==0:
mat[mx][my] = 1 # 장애물
stop_spread[idx] = (r+move[d][0], c+move[d][1], d, v) # x,y,d,v
else:
del stop_spread[idx] # 제거
if mat[px][py]==0: # 이동가능
que.append((px, py, cnt+1))
visited[px][py] = True
elif mat[px][py]==4: # 탈출구
return cnt+1
return -1
아래 처럼
if 0<=px<n and 0<=py<n and not visited[px][py]:
if cnt+1 > g_cnt: # 다음초로 넘어갔다면
g_cnt += 1 # 시간초 증가
for idx, stop in enumerate(stop_spread):
r, c, d, v = stop
if g_cnt%v == 0: # 움직일 차례면
mx, my = r+move[d][0], c+move[d][1]
if 0<=mx<n and 0<=my<n and mat[mx][my]==0:
mat[mx][my] = 1 # 장애물
stop_spread[idx] = (r+move[d][0], c+move[d][1], d, v) # x,y,d,v
else:
del stop_spread[idx] # 제거global_cnt인 g_cnt를 두어서, 현재 시간초가 종료하여 다음 시간초가 진행된다면
미리 "이상현상"을 진행하여 막기
전체코드
# d: 0(동), 서(1), 남(2), 북(3)
# 목표: (장애물, 시간 이상 현상)을 피해 탈출구로, 최소 시간, -1
# 만약에 시간이 지나면 탈출구가 잠길 수 있음, 그러면 탈출 실패
from collections import deque
move = [(0,1),(0,-1),(1,0),(-1,0)]
n, m, f = map(int, input().split())
mat = [0]*n
for i in range(n):
mat[i] = list(map(int, input().split()))
time_wall = [[5]*(3*m+2) for _ in range(3*m+2)]
for i in range(3*m+2):
time_wall[0][i] = 9
time_wall[3*m+1][i] = 9
time_wall[i][0] = 9
time_wall[i][3*m+1] = 9
# 동
c_mat = [0]*m
cc_mat = [[0]*m for _ in range(m)]
for i in range(m):
c_mat[i] = list(map(int, input().split()))
for i in range(m):
for j in range(m):
cc_mat[m-1-j][i] = c_mat[i][j]
for i in range(m):
for j in range(m):
time_wall[m+1+i][2*m+1+j] = cc_mat[i][j]
# 서
c_mat = [0]*m
cc_mat = [[0]*m for _ in range(m)]
for i in range(m): # 서
c_mat[i] = list(map(int, input().split()))
for i in range(m):
for j in range(m):
cc_mat[j][m-1-i] = c_mat[i][j]
for i in range(m):
for j in range(m):
time_wall[m+1+i][1+j] = cc_mat[i][j]
# 남
for i in range(m):
arr = list(map(int, input().split()))
for j in range(m):
time_wall[2*m+1+i][m+1+j] = arr[j]
# 북
c_mat = [0]*m
cc_mat = [[0]*m for _ in range(m)]
for i in range(m):
c_mat[i] = list(map(int, input().split()))
for i in range(m):
for j in range(m):
cc_mat[m-1-i][m-1-j] = c_mat[i][j]
for i in range(m):
for j in range(m):
time_wall[i+1][m+1+j] = cc_mat[i][j]
# 윗면
for i in range(m):
arr = list(map(int, input().split()))
for j in range(m):
time_wall[m+1+i][m+1+j] = arr[j]
stop_spread = []
for i in range(f): # 시간 이상 현상 초기 위치
r,c,d,v = map(int, input().split()) # 위치, 방향, 확산상수
mat[r][c] = 1
stop_spread.append((r,c,d,v))
def time_exit_bfs(i, j):
que = deque()
que.append((i,j))
visited = [[False]*n for _ in range(n)]
visited[i][j] = True
exit_x, exit_y = 0, 0
while que:
x, y = que.popleft()
for dx, dy in move:
px, py = x+dx, y+dy
if 0<=px<n and 0<=py<n and not visited[px][py]:
if mat[px][py] == 3:
que.append((px, py))
visited[px][py] = True
elif mat[px][py] == 0: # 탈출구
exit_x, exit_y = px, py
return [exit_x, exit_y]
def side_mapping(x, y):
if x == m+1:
if y < m+1: # 1 -> 2
return y, x
elif y > 2*m: # 4 -> 3
return m+1-(y-(2*m)),2*m
elif x == 2*m:
if y < m+1: # 5 -> 6
return 2*m+y,m+1
elif y > 2*m: # 7 -> 8
return y, x
elif y == m+1:
if x < m+1: # 2 -> 1
return y, x
elif x > 2*m: # 6 -> 5
return 2*m, x-(2*m)
elif y == 2*m:
if x < m+1: # 3 -> 4
return m+1, 2*m+x
elif x > 2*m: # 8 -> 7
return y, x
def time_bfs(i, j):
que = deque()
que.append((i,j,0))
visited = [[False]*(3*m+2) for _ in range(3*m+2)]
visited[i][j] = True
flag = 0
sec = -1
while que:
x, y, cnt = que.popleft()
for dx, dy in move:
px, py = x+dx, y+dy
if 0<=px<3*m+2 and 0<=py<3*m+2 and not visited[px][py]:
if time_wall[px][py] == 5: # 측면이동
visited[px][py] = True # 방문 처리
px, py = side_mapping(x, y) # 옆면으로
if not visited[px][py]:
if time_wall[px][py] == 0:
que.append((px, py, cnt+1))
visited[px][py] = True
elif time_wall[px][py] == 7: # 시간의 벽 탈출
flag = 1
sec = cnt # 시간초
break
elif time_wall[px][py] == 0:
que.append((px, py, cnt+1))
visited[px][py] = True
elif time_wall[px][py] == 7: # 시간의 벽 탈출
flag = 1
sec = cnt # 시간초
break
if flag == 1:
break
return sec
def time_wall_mapping(i ,j):
if i<0:
time_wall[0][m+1+j] = 7 #북
elif i>=m:
time_wall[3*m+1][m+1+j] = 7 #남
elif j<0:
time_wall[m+1+i][0] = 7 # 서
else:
time_wall[m+1+i][3*m+1] = 7 # 동
def bfs(i, j, c):
que = deque()
que.append((i,j,c))
visited = [[False]*n for _ in range(n)]
visited[i][j] = True
g_cnt = c # 글로벌 시간초
while que:
x, y, cnt = que.popleft()
for dx, dy in move:
px, py = x+dx, y+dy
if 0<=px<n and 0<=py<n and not visited[px][py]:
if cnt+1 > g_cnt: # 다음초로 넘어갔다면
g_cnt += 1 # 시간초 증가
for idx, stop in enumerate(stop_spread):
r, c, d, v = stop
if g_cnt%v == 0: # 움직일 차례면
mx, my = r+move[d][0], c+move[d][1]
if 0<=mx<n and 0<=my<n and mat[mx][my]==0:
mat[mx][my] = 1 # 장애물
stop_spread[idx] = (r+move[d][0], c+move[d][1], d, v) # x,y,d,v
else:
del stop_spread[idx] # 제거
if mat[px][py]==0: # 이동가능
que.append((px, py, cnt+1))
visited[px][py] = True
elif mat[px][py]==4: # 탈출구
return cnt+1
return -1
# 1) 나가는 출구 찾기
flag = 0
time_exit = 0
start_x, start_y = 0, 0
for i in range(n):
for j in range(n):
if mat[i][j] == 3:
time_exit = time_exit_bfs(i, j)
start_x, start_y = i, j
flag = 1
break
if flag == 1:
break
# 2) 시간의 벽에다가 값으로 매핑하기
time_wall_mapping(time_exit[0]-start_x, time_exit[1]-start_y)
# 3) 시간의 벽 탈출하기
result = -1 # 시간초
flag = 0
for i in range(3*m+2):
for j in range(3*m+2):
if time_wall[i][j] == 2: # 타임머신 장소
temp_sec = time_bfs(i, j)
if temp_sec == -1: # 장애물로 탈출 불가능
flag = 1
else:
result = temp_sec
# 4) 시간의 벽에서 나왔는데 이상현상이 막으면 탈출실패
delete_num = []
for idx, stop in enumerate(stop_spread):
r, c, d, v = stop
value = result//v # 움직인 거리
if value > 0: # 확산해야 한다면
for i in range(1, value+1):
px, py = r+(move[d][0]*i), c+(move[d][1]*i)
if 0<=px<n and 0<=py<n and mat[px][py]==0:
mat[px][py] = 1 # 장애물
else:
delete_num.append(idx) # 삭제
break # 탈출
stop_spread[idx] = (r+(move[d][0]*value), c+(move[d][1]*value), d, v) # x,y,d
temp = []
for idx in range(len(stop_spread)):
if idx not in delete_num:
temp.append(stop_spread[idx])
stop_spread = temp[:]
if flag == 1 or mat[time_exit[0]][time_exit[1]] == 1: # 시간의 벽 탈출못하면 or 이상현상이 막으면
print(result)
else:
# 5) 미지의 벽 탈출하기(이상현상 고려하면서)
result = bfs(time_exit[0], time_exit[1], result+1)
print(result)실수한 내용 + 자가 피드백
- (3*m+2)*(3*m+2) 배열, n*n 배열 => 2개가 있었는데 BFS돌릴 때 복붙하다가 0<= px < n조건도 복붙같이 돼서 틀렸음.
- 변수의 혼합 사용(px,py남발하다가, bfs()에서 px변수가 겹쳐서 mx로 고침)
- 미지의 영역을 움직일 때, 현재 움직인 거리도 넣었는데 문제를 잘 읽어보면 그냥 해당 주기될때마다(%v==0) +1만 이동하면 됨.
- 패딩전략 좋았고, 2차원 전개도 전략 좋았지만 구현에서 시간 많이 잡아먹음, 따라서 손으로 바로 그리고 숫자로 직접 대입할 것
- 2차원 돌리기는 그림그려서 직접 숫자 매칭해보는게 가장 빠름
- 중간중간 더 적극적으로 디버깅 시행하는게, 전체 해결 시간에 더 이로움, 문제가 절차적 구현일수록 더욱 함수화해서 쪼개서 문제 바라볼 것(side_mapping에서 틀렸던 점을 하나하나씩 다 디버깅해서 보는게 더 오래걸렸음, 미리 직접 숫자대입으로 노가다처럼 휴먼에러 많이 터지는 과정을 (함수화->숫자매핑)하고 넘어가자
'Programming > Algorithm(Python)' 카테고리의 다른 글
| [백준/python][구현] 8972번 - 미친 아두이노 (0) | 2025.05.21 |
|---|---|
| [코드트리/python] 고대 문명 유적 탐사(2024년 상반기 삼성기출) (0) | 2025.04.12 |
| [삼성공채] Python 준비하기 (0) | 2025.04.06 |
| [백준/python][백트래킹] 18429번 - 근손실 (0) | 2025.01.23 |
| [프로그래머스] 섬 연결하기 LV3[prim, union-find] (0) | 2024.02.16 |
