[Python][백준] 13549번 숨바꼭질 3

https://www.acmicpc.net/problem/13549

공부 날짜 : 2023.02.07
정답 참조 여부 : X

1차원 직선상에서 현재 위치와 목적 위치가 주어지고 현재위치에서 +1, -1 *2의 위치로 이동 가능할 때 목적위치까지 도달하는 최단거리를 구하는 문제이다.

---

방금 푼 숨바꼭질 2 문제와 똑같은 문제로 봐도 무방하다.

딱 하나 차이점은 순간이동시 시간이 소모되지 않는다는 것

이거 때문에 코드의 완성은 만족스럽지 못하다.

visit에 dis가 순서대로 입력된다면, 가장 먼저 발견된 x == k 일때 최단거리가 된다.

하지만 순간 이동시 시간소모가 없기때문에 visit에 추가되는 dis는 순서가 정렬되어있지 않다. 그래서 아마 코드에서 방문 가능한 모든위치를 탐색했을 것이다.

결과적으로 코드가 정답으로 나오긴 했지만, 많이 찝찝함이 남아있다. 방문 가능한 모든 위치를 탐색해 봤을텐데, 그게 과연 최소경로일지 확신이 들지 않는다. 최근 백준에대한 신뢰도가 많이 낮아졌다. 데이터 케이스가 과연 다 있을까...

소스코드

import sys
input = sys.stdin.readline
from collections import deque
#############################################
n, k = map(int, input().split())

# 시작점과 거리를 초기값으로 저장
visit = deque()
visit.append((n, 0))

# 방문 여부를 판단하는 배열
visited = [False for _ in range(100001)]
visited[n] = True

# 정답이 저장될 두 변수
ans_dis = 100001
# ans_count = 0

# 다음 탐색한 장소가 있을 때 순환
while visit:
    x, dis = visit.popleft()
    # 현재 위치 방문 처리
    visited[x] = True
    # 최단거리 이상의 거리는 탐색할 필요 없으므로 반복 중단
    # if ans_dis < dis:
    #     break

    # 목적지 탐색시 거리와 개수 +1
    if x == k and ans_dis > dis:
        ans_dis = dis
        # ans_count += 1


    # if ans_dis == dis:
    #     continue

    # 현재 장소에서 이동가능하고, 이전에 방문하지 않은 모든 칸 추가
    if 0 <= x+1 <= 100000 and not visited[x+1]:
        visit.append((x+1, dis+1))

    if 0 <= x-1 <= 100000 and not visited[x-1]:
        visit.append((x-1, dis+1))

    if x < k and 0 <= x*2 <= 100000 and not visited[x*2]:
        visit.append((x*2, dis))

print(ans_dis)