[ SWEA 1953 ] 탈주범 검거 (파이썬)
SW Expert Academy 문제 풀러 가기
1. 문제 요약
- 탈주범이 맨홀로 도망쳤다!
탈주범이 들어간 맨홀의 위치와 서로 연결된 터널의 정보가 주어집니다. 탈주범은 시간당 1만큼 이동할 수 있을 때, 현재 시간(L)에 탈주범이 존재할 수 있는 모든 장소의 갯수를 구하는 문제입니다.
$ INPUT
`지하 터널 지도의 세로 크기 N`
`가로 크기 M`
`맨홀 뚜껑이 위치한장소의 세로 위치 R`
`가로 위치 C`
`탈출 후 소요된 시간 L`
터널의 종류
예시
빨간색 맨홀로 들어간 탈주범이 3시간후에 있을 수 있는 장소의 수는 다음과 같이 다섯 개 입니다.
2. 풀이
from collections import deque
# 각각의 터널 종류를 딕셔너리를 이용해서 표현해 줍니다.
tunnel = {
0: (),
1: ((1, 0), (0, 1), (-1, 0), (0, -1)),
2: ((1, 0), (-1, 0)),
3: ((0, 1), (0, -1)),
4: ((-1, 0), (0, 1)),
5: ((1, 0), (0, 1)),
6: ((1, 0), (0, -1)),
7: ((-1, 0), (0, -1))
}
for tc in range(1, int(input())+1):
N, M, R, C, L = map(int, input().split())
board = [list(map(int, input().split())) for _ in range(N)]
q = deque([(R,C)])
visit = [[0] * M for _ in range(N)]
visit[R][C], cnt = 1, 1
# 너비우선으로 탐색
while q:
x, y = q.popleft()
for dx, dy in tunnel[board[x][y]]:
nx, ny = x + dx, y + dy
if not 0 <= nx < N or not 0<= ny < M:continue # 예외처리 1) 모서리
if (-dx, -dy) in tunnel[board[nx][ny]]: # 예외처리 2) 연결부
if not visit[nx][ny] and board[nx][ny]:
visit[nx][ny] = visit[x][y] + 1
q += [(nx, ny)]
if visit[nx][ny] <= L:cnt += 1
print(f'#{tc} {cnt}')
3. 감상
이 문제의 해결 포인트는 다음과 같습니다.
- 터널의 모양을 어떻게 표현할 것인가
- 터널의 연결을 어떻게 표현할 것인가
저는 1의 처리에 딕셔너리를 이용해서 7가지 모양을 각각 이동 가능한 델타값으로 설정하는 것으로 해결했습니다.
2의 연결부분을 처리하는 데에는 제가 정의한 1의 딕셔너리에서 이어져있는 두 개의 터널은 서로 (-x, -y)의 관계를 가지고 있다는 것을 발견하여 간단하게 해결하였습니다.
평이한 난이도의 문제이지만 아이디어도 재밌고, 구현할 거리가 있는 훌륭한 문제입니다.
공유하기!