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

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

13549번: 숨바꼭질 3

 

풀이 과정

1697 - 숨바꼭질 문제와 비슷하다. 차이점은 숨바꼭질 3 문제는 순간이동할 때 0초 소요된다.

숨바꼭질 문제를 예전에 풀어서 날로 먹으려 순간이동 부분만 코드를 수정했는데 틀렸다.

다시 짜야하나 싶었는데 조금만 수정하니까 해결됐다. bfs로 해결함.

 

from collections import deque
N , K = map(int,input().split())


deq = deque()
deq.append([N,0])
visited = [N]

while True:
    X = deq.popleft()
    posi = X[0]
    second = X[1]

    if posi == K:
        print(second)
        break

    if posi * 2 >= 0 and posi * 2 <= 100000 and posi * 2 not in visited:
        visited.append(posi * 2)
        deq.append([posi * 2,second])
    if posi - 1 >= 0 and posi - 1 <= 100000 and posi - 1 not in visited:
        visited.append(posi - 1)
        deq.append([posi - 1,second + 1])
    if posi + 1 >= 0 and posi + 1 <= 100000 and posi + 1 not in visited:
        visited.append(posi + 1)
        deq.append([posi + 1,second + 1])

큐에서 pop를 한 값에 따라 posi * 2, posi - 1, posi + 1을 각 조건에 확인해서 큐에 추가해주면 된다.

주의할 점은 큐에 추가할 때 순간 이동하는 부분은 먼저 넣어줘야 한다.

 

예를 들어 N과 K 값이 3, 5 인경우를 생각해보자

탐색을 X - 1, X + 1, X * 2 순으로 bfs 하면 

3

2 4 6

1 (3) (4) / (3) 5 8 / (5) 7 12             //괄호는 이미 방문해서 방문 안 함.

위와 같이 방문하면 걸린 시간은 +1 +1 이므로 2를 출력한다. 

 

다른 방법으로 탐색을 X * 2, X - 1, X + 1 순으로 하면

3

6 2 4

12 5 7 / 8 (3) (5) / (4) 1 (3)

위와 같이 방문하면 순간이동은 0초 이므로 1을 출력한다.

 

따라서 0초 걸리는 순간이동을 먼저 방문해야 된다.

나머지는 숨바꼭질 1과 똑같음.

전체 코드는 위