백준 1697 python [숨바꼭질]

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

이번 문제는 최단거리를 구하는 문제였는데,

BFS로도 최단거리를 구할 수 있다길래 신기했다.

간선에 가중치가 없다고 가정했을 때는 BFS로 가능하다고 한다.

제일 먼저 방문하는게 최단거리다.

from collections import deque

# with open("./data.txt", "r") as f:
#     data = f.readline()

N, K = map(int, input().split())
MAX = 10 ** 5
visited = [0]* (MAX+1)

def bfs(n):
    q = deque()
    q.append(n)
    
    while q:
        a = q.popleft()
        
        if(a == K):
            q.clear()
            return visited[a]
        
        for i in (a-1, a+1, a*2):
            if(i >= 0 and i <= MAX and visited[i] == 0):
                q.append(i)
                visited[i] = visited[a] + 1
    
print((bfs(N)))
    

풀이

이번 문제는 다른 사람의 소스를 참고하면서 풀었다.

다른 bfs와 마찬가지로 큐에 담아주면서 진행하면 된다.

현재 방문하려는 노드를 방문한 적이 없고

0보다 크고 (배열의 인덱스 때문에)

MAX 값보다 작다면 (배열의 최대 크기를 동생의 위치로 선언한다면
동생의 위치 + 1 > -1하는게 최단 거리일 경우에는 찾을 수 없기에)

큐에 넣어준다.

근데 반복문을 돌면서 -1, +1, *2 해주면 되겠는데 어떤 방식이 있을까 했는데

파이썬은 for i in (a-1, a+1, a*2) 이게 가능하네. 신기하다

// 다시 보는데 q.clear()는 굳이 필요 없을 듯 하긴하다.