BFS의 충분조건? : 모든 엣지의 가중치가 동일할 것.

#13549 숨바꼭질3 https://www.acmicpc.net/problem/13549

13549번: 숨바꼭질 3

 

신기한 문제였다.  BFS를 공부하다가 만난 문제이지만 사실 BFS를 통한 풀이가 온전한 풀이가 아니라는것.

문제는 점프라는 행위에 있다.

다른 행위와는 달리 점프에 소요되는 비용은 0이다.

그래프 내에서 가중치가 0이라는 말이다.

모든 엣지의 가중치가 동일할 때 정확한 수행능력을 보여주는게  BFS알고리즘이다.

그렇기 때문에 가중치가 다른 위 문제에서는 오류가 발생하기 쉽다.

 

정확한 해법

- 디익스트라 알고리즘 (뭔지모름)

- 0-1 BFS (뭔지 모름) : 가중치가 0인 간선에 연결된 정점은 큐의 맨 뒤가 아닌 맨 앞에 넣는 방법

- *2를 별도의 간선으로 생각하지 않고,  +1이나  -1에 의한 좌표를 큐에 넣을 때 그 좌표의 거듭제곱 배인 좌표들을 전부 큐에 넣는 방법

 

위 세가지 방법으로 해결할 수 있다고 한다. 나중에 더 알아보자.

참조 : https://www.acmicpc.net/board/view/38887#comment-69010

 

N, T = map(int, input().split())
M = 10**5

dist = [0]*(M+1)


def solve(position):
    que = []
    que.append(position)

    while que:
        p = que.pop(0)
        if p == T:
            return p

        for np in [p*2, p-1, p+1]:
            if 0 <= np <= M and not dist[np]:
                if np == p*2:
                    dist[np] = dist[p]
                    que.append(np)
                else:
                    dist[np] = dist[p]+1
                    que.append(np)


solve(N)

print(dist[T])

일단 내가 많은 자료들을 찾아보며 작성한 코드이다.

처음에는 다른 숨바꼭질 문제들과 다를 바 없이 p-1부터 시작했는데 틀린 답이 나왔다.

p*2부터 시작하면 정답이 나온다는 사실이 조금 당황스러웠는데

위에서 제시한 세 가지 방법 중 마지막 방법과 조금 연관이 있을거라 짐작해본다.