2412번: 암벽 등반
어떤 암벽에 n(1 ≤ n ≤ 50,000)개의 홈이 파져 있다. 각각의 홈의 좌표는 (x, y)와 같이 표현되는데, |a - x| ≤ 2이고 |b - y| ≤ 2이면 (x, y)에서 (a, b)로 이동할 수 있다. 이와 같이 홈들을 이용하여 이동
www.acmicpc.net
문제
어떤 암벽에 n(1 ≤ n ≤ 50,000)개의 홈이 파져 있다. 각각의 홈의 좌표는 (x, y)와 같이 표현되는데, |a - x| ≤ 2이고 |b - y| ≤ 2이면 (x, y)에서 (a, b)로 이동할 수 있다. 이와 같이 홈들을 이용하여 이동하면서 y = T(1 ≤ T ≤ 200,000)일 때까지, 즉 암벽의 정상까지 오르려고 한다.
현재 당신이 있는 위치는 (0, 0)이다. 이 위치에서 시작하여 이동 회수를 최소로 하면서 정상에 오르려고 한다. 정상에 오를 때의 x좌표는 아무 것이나 되어도 상관이 없다.
입력
첫째 줄에 n, T가 주어진다. 다음 n개의 줄에는 각 점의 x, y좌표가 주어진다. 두 좌표는 모두 0이상이며, x좌표는 1,000,000이하, y좌표는 T이하이다. 입력에 현재 위치인 (0, 0)은 주어지지 않는다.
출력
첫째 줄에 최소 이동 회수를 출력한다. 만약, 정상에 오를 수 없으면 -1을 출력한다.
코드
import sys
input = sys.stdin.readline
from collections import deque, defaultdict
n, t = map(int, input().split())
wall = defaultdict(list)
for _ in range(n):
x, y = map(int, input().split())
wall[y].append(x)
q = deque([(0, 0, 0)])
while q:
x, y, cnt = q.popleft()
if y == t: # 정상에 오르기 성공
print(cnt)
exit()
for b in range(-2, 3):
if y+b in wall:
remove_lst = []
for a in wall[y+b]:
if abs(a-x) <= 2:
q.append((a,y+b,cnt+1))
remove_lst.append(a)
# 이용한 홈 리스트에서 제거 -> 방문처리
for r in remove_lst:
wall[y+b].remove(r)
print(-1)
BFS를 응용하여 풀이하였다.
입력받은 홈들의 정보를 y 좌표를 키, x 좌표들 리스트를 값으로 갖는 defaultdict(wall)에 저장해준다.
그리고 deque에 처음 위치와 이동횟수를 담은 튜플 (0, 0, 0)을 넣어주고 BFS를 돌린다.
y 좌표가 위아래로 -2 ~ 2인 홈들에 대해 살펴보며 이동할 수 있는 홈의 경우 큐에 추가하고 리스트에서 지워준다.
y 좌표가 T와 같은 값이 나온다면 정상에 도달한 것이므로 cnt 값을 출력하고 프로그램을 종료한다. 만약 중간에 종료되지 못하고 q가 비어서 while문이 끝나게 된다면 정상에 오를 수 없는 경우이므로 -1을 출력해준다.
'문제풀이 > DFS_BFS' 카테고리의 다른 글
[Python/파이썬] 백준 4179번 불! (0) | 2023.07.16 |
---|---|
[Python/파이썬] 백준 13565번 침투 (0) | 2023.07.03 |
[Python/파이썬] 백준 16508번 전공책 (0) | 2023.06.24 |
[Python/파이썬] 백준 2636번 치즈 (0) | 2023.06.23 |
[Python/파이썬] 백준 5547번 일루미네이션 (0) | 2023.06.23 |