[백준] 1697번: 숨바꼭질

수빈이와 동생 사이의 엣지의 개수를 세주면된다. (최단거리!)

나는 처음에 그래프를 만들어서 하려고 했는데 사실 그럴 필요가 없었다.

특정 노드에 어떤 노드가 연결되어있는지는 굳이 확인하지 않아도 알 수 있기 때문에 그래프를 만들 필요가 없다. 수빈이가 지금 있는 곳이 5라고 하면 갈 수 있는(연결된) 노드는 4, 6, 10 이라는 걸 그냥 구할 수 있다.

그래서 bfs 함수를 만들 때 현재 번호의 범위에 따라 최대 3개까지의 수를 큐에 넣어주면 되는 간단한 문제였다.

from _collections import deque

def bfs(N, K):
    queue = deque([[N, 0]]) # [노드 번호, 최단거리]
    visited = [False]*1000001
    while queue:
        curr = queue.popleft()
        if curr[0] == K:
            return curr[1]
        if not visited[curr[0]]:
            visited[curr[0]] = True
            if curr[0] <= 999999:
                queue.append([curr[0] + 1, curr[1] + 1])
            if curr[0] > 0:
                queue.append([curr[0] - 1, curr[1] + 1])
            if curr[0] <= 500000:
                queue.append([curr[0] * 2, curr[1] + 1])

N, K = map(int, input().split())
print(bfs(N, K))

👇🏻 다 똑같은데 시간초과가 났던 코드 (visited 여부 확인 방법을 다르게 했음)

from _collections import deque

def bfs(N, K):
    queue = deque([[N, 0]])
    visited = []
    while queue:
        curr = queue.popleft()
        if curr[0] == K:
            return curr[1]
        if curr[0] not in visited: # O(len(visited))
            visited.append(curr[0])
            if curr[0] <= 500000:
                queue.append([curr[0] * 2, curr[1] + 1])
            if curr[0] <= 999999:
                queue.append([curr[0] + 1, curr[1] + 1])
            if curr[0] > 0:
                queue.append([curr[0] - 1, curr[1] + 1])


N, K = map(int, input().split())
print(bfs(N, K))