[백준] 13549번 숨바꼭질 3 ( 파이썬)

 

문제

 

13549번: 숨바꼭질 3

 

 

 

 

정답 소스코드 (Python)

 

from collections import deque
n,k=map(int,input().split())
limit=100001
cnt=[0]*limit
visited=[False]*limit
def bfs(x,end):
    queue=deque()
    queue.append(x)

    while queue:
        x=queue.popleft()
        if x==end:return cnt[x]
        if -1<x*2<limit and visited[x*2]==0 :
            queue.appendleft(x*2)
            cnt[x*2]=cnt[x]
            visited[x*2]=True
        if -1<x-1<limit and visited[x-1]==0 :
            queue.append(x-1)
            cnt[x-1]=cnt[x]+1
            visited[x-1]=True
        if -1<x+1<limit and visited[x+1]==0 :
            queue.append(x+1)
            cnt[x+1]=cnt[x]+1
            visited[x+1]=True



print(bfs(n,k))

 

 

 

 

풀이  (Python)

 

 

문제의 경우 간단하다. 수빈이와 동생의 위치가 주어지며 수빈이가 동생을 따라잡으면 된다.

찾는데 걸리는 가장 짧은 시간을 찾으면 되기에  최단시간 or 최단 거리 -> BFS, 다익스트라 , dp 등이 있지만, 문제가 단순해 보여 BFS로 풀이와 같이 생각하여 풀이했다.

 

 

 

Point 1)  우선순위 큐 활용한 BFS(너비 우선 탐색)

 

        if -1<x*2<limit and visited[x*2]==0 :
            queue.appendleft(x*2)
            cnt[x*2]=cnt[x]
            visited[x*2]=True
        if -1<x-1<limit and visited[x-1]==0 :
            queue.append(x-1)
            cnt[x-1]=cnt[x]+1
            visited[x-1]=True
        if -1<x+1<limit and visited[x+1]==0 :
            queue.append(x+1)
            cnt[x+1]=cnt[x]+1
            visited[x+1]=True

 

 

위치의 변화의 +1과 -1과 *2가 시간 추가가 다른 것이 포인트인 문제이다. *2를 했을 때에는 시간 추가가 되지 않아야

한다. visitied 방문체크를 하지 않는 다면 시간초과가 발생한다. 하지만 +1과 -1과 *2를 모두 똑같이 BFS로 탐색하게 된다면, +1로 찾은 칸은 *2로 갈 수 있었음에도 불구하고, 이미 방문 처리가 되어 있기에 *2로 찾을 수 없게 된다. 이를 해결하기 위해 *2를 더 먼저 처리하여야 한다. 

이를 해결하기 위해 queue에 push 할 때 queue.appendleft()를 사용하여 맨 왼쪽에 추가하는 방식으로 진행한다.

 

 

 

 

Point 2)  +1을 먼저 해야 할까 -1을 먼저 해야 할까?

 

BFS로 탐색할 때 최단시간 등을 계산해야 한다면, 유리한 순서로 계산해야 최단시간 or 최단 거리를 찾을 수 있다.

 

case 1) 수빈이가 동생보다 오른쪽에 있는 경우

-1의 방법으로 밖에 갈 수 없기 때문에 1가지의 경우만 존재한다.

 

case 2) 동생이 수빈이 보다 오른쪽에 있는 경우

-1, +1, *2 모두 사용하여 수빈이가 동생을 찾아야 한다.

+1이 더 오른쪽으로 갈 수 있으니까 먼저 사용하여 queue에 넣어야 하지 않을까?

 

아니다. *2가 우선적으로 된다는 사실을 잊으면 안 된다. *2 사이에 +또는 -를 섞었을 때 수빈이는 3위 치, 동생은 10에 있다고 했을 때를 비교하면,

 

3->6->5->10                                         (-1을 먼저 한 경우)

3->6->7->14 or 3->6->7->8->9->10    (+1을 먼저 한 경우)

 

-1을 한 이후 *2를 하였을 때 더 적은 폭으로 *2를 활용할 수 있는 사실을 위에서 파악할 수 있다.

이를 통해 if문 순서(queue에 삽입하는 순서)는 +1보다 -1을 먼저 진행해야 한다. (*2는 우선순위가 있기에 상관없다.)

 

 

 

 

 

※ 추천 반례

 입력: 1 4
 정답: 0

 입력: 1 5
 정답: 1

 입력: 1 33
 정답: 1