백준 13549번: 숨바꼭질 3 Python 풀이 및 정답 코드

문제 링크

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

13549번: 숨바꼭질 3

 

 

 

문제 설명

문제

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 0초 후에 2*X의 위치로 이동하게 된다.

수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오.

입력

첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다.

출력

수빈이가 동생을 찾는 가장 빠른 시간을 출력한다.

 

숨바꼭질2와 비슷하지만 2*x로 이동하는 시간이 0초가 되었다.

 

 

 

문제 풀이

사실 이미 한번 푼적이 있다.
https://he11owor1d.tistory.com/36

백준 12865, 13549, 1504, 14891, 1981번 파이썬 풀이

그런데 전혀 생각이 안나서 처음부터 다시 풀었다.

처음 생각한 풀이 방법은
1. 현재 방문한 위치에서 0초 만에 갈 수 있는 위치들의 최단시간을 기록하고 큐에 넣는다. (현재 방문 위치가 5이면 5, 10, 20, 40, 80, 160 ... 해서 100,000 전까지 모두)
2. x-1, x+1 을 방문한다.

from collections import deque
from math import log

N, K = map(int, input().split())

visited = [-1] * 100001
visited[N] = 0
q = deque([N])

while q:
    x = q.popleft()
    if x == K:
        print(visited[x])
        break
    # 방문한 위치에 대해서 0초만에 갈 수 있는 곳들의 최단시간을 전부 채워준다
    for t in [N * 2 ** i for i in range(int(log(int(100000 / N), 2)) + 1)]:
        # 방문한 적이 없는 위치만 채워 줌
        if visited[t] == -1:
            visited[t] = visited[x]
            q.append(t)
        t *= 2
    for a in [x - 1, x + 1]:
        if 0 <= a <= 100000 and visited[a] == -1:
            visited[a] = visited[x] + 1
            q.append(a)

틀렸음 당연함

아래처럼 코드를 고치고 나서 이전에 풀었던 걸 봤는데 접근 방식은 같다.
대신 구현이 잘못됐는데, 포인트는 큐에서 뒤로 갈 수록 시간이 오래 걸렸어야 했는데 위에처럼 해버리면 섞여버려서 틀린거다.
간단하게 하려면 포문 돌려서 2*x를 몽땅 큐에 넣어버리는게 아니라, 2*x로 갈 수 있는 위치는 그냥 큐의 앞에 넣어서 바로 다음에 방문해버리면 된다. 어차피 현재 위치까지 도달한 시간과 같으니까...
이렇게 하려면 이 링크 혹은 이 글 가장 밑에서 정답 코드를 확인할 수 있다.

이번엔 방법이 생각 안나서 그냥 클래식하게 풀었다.
꼭 지켜야할 원칙은 visited에는 항상 '최단 시간'만 기록되어야 한다는 것이다.
1. 가장 기본적인 숨바꼭질 문제와 같이 세 곳을 방문한다.
2. x-1, x+1에는 이전 시간 + 1을, 2*x에는 이전 위치와 같은 시간을 넣어준다.
3. 이번 문제가 이전 것과 달라서 고려해야 할 점은 이전에 이미 방문한 위치라도 이번이 더 빠르게 도달했을 경우도 있다는 것이다. (큐의 순서가 시간을 보장하지 못하므로) 따라서 이전 시간과 현재 도달 시간을 비교헤서 더 빠른걸 넣어줘야 한다.

코드는 다음과 같다.

 

 

 

코드

from collections import deque

N, K = map(int, input().split())

visited = [-1] * 100001
visited[N] = 0
q = deque([N])

while q:
    x = q.popleft()
    if x == K:
        print(visited[x])
    for a in [2 * x, x - 1, x + 1]:
        if 0 <= a <= 100000:
            if visited[a] == -1:
                visited[a] = visited[x] if a == 2 * x else visited[x] + 1
                q.append(a)
            else:
                visited[a] = min(
                    visited[a], visited[x] if a == 2 * x else visited[x] + 1
                )

 

 

 

결과

 

 

 

다른 사람의 코드

from collections import deque

n, k = map(int, input().split())
q = deque()
q.append(n) 
visited = [-1 for _ in range(100001)]
visited[n] = 0

while q:
    s = q.popleft()
    if s == k:
        print(visited[s])
        break
    if 0 <= s-1 < 100001 and visited[s-1] == -1:
        visited[s-1] = visited[s] + 1
        q.append(s-1)
    if 0 < s*2 < 100001 and visited[s*2] == -1:
        visited[s*2] = visited[s]
        q.appendleft(s*2)
    if 0 <= s+1 < 100001 and visited[s+1] == -1:
        visited[s+1] = visited[s] + 1
        q.append(s+1)

쉽게 생각해낼순 없지만 이렇게 하면 간단하다.

 

 

 

리뷰