[백준] 13549 숨바꼭질 3 - BFS

jckim22·2023년 7월 17일

BFS 백준 알고리즘

[ALGORITHM] STUDY (PS)

목록 보기

32/86

난이도

Gold 5

풀이 참고 유무

?

막힌 부분

가중치가 다른 간선을 고려하지 않았음

문제

문제 바로가기

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

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

입력

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

출력

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

예제 입력

5 17

예제 출력

2

문제 검토

숨바꼭질1 문제와 차이점은 가중치가 1 1 1 에서 0 1 1으로 다르다는 것이다.

풀이(python)

Python

from sys import stdin
n,k=map(int,stdin.readline().split())
visited = [0 for _ in range(100001)]
check = [False for _ in range(100001)]
if n==k:
    print(0)
    exit()
from collections import deque

def BFS():
    q=deque()
    q.append(n)
    while q:
        su=q.popleft()
        move = [su*2,su-1,su+1]
        if su==k:                
            return
        for mv in move:
            if mv<0 or mv>100000:
                continue
            if check[mv]:
                continue
            check[mv]=True
            if mv==su*2:
                visited[mv]=visited[su]
                q.append(mv)
            else:
                visited[mv]=visited[su]+1
                q.append(mv)
                    
BFS()                    
print(visited[k])

숨바꼭질 1에서 check리스트를 추가로 사용한다.
숨바꼭질 1에서는 visited==0으로 방문을 구별했다.

하지만 이 문제에서 2*n 일 경우 +0초 이기 때문에 check 리스트를 매핑해서 시간이 증가하지 않았더라도 방문 체크를 할 수 있도록 한다.

가장 중요한 부분은 덱에 담기는 순서이다.
2*su가 먼저 탐색이 되어야 한다.

2*su로 도착하게 된다면 3이 정답인 경우가 있다고 하자
만약 1+su를 먼저 덱에 넣고 탐색하게 된다면 4인 경우의 답이 나올 수도 있다.

걸린 시간

26:44

총평

문제를 다 풀고 다른 사람의 코드를 보는 도중 출제자의 다음과 같은 댓글을 보게 되었다.
나는 아래 방법중 2번째 방법으로 해결했다.

이후에 다익스트라로 다시 풀어봐야겠다.

원래 이 문제는 단순한 BFS를 요구하는 문제가 아닙니다. 왜냐하면, BFS를 하기 위해서는 모든 간선의 가중치가 동일해야 한다는 전제 조건이 필요하기 때문입니다. 이 문제는 가중치가 0인 간선이 있기 때문에 일반적으로는 단순한 BFS를 쓸 수 없으나, 문제의 특성 때문에 방문 순서에 따라서 단순 BFS로도 우연히도 항상 정답을 찾을 수 있을 뿐입니다. 왜 하필 이 순서로 하면 항상 정답이 나오는가를 증명하는 건 매우 복잡한 일입니다.