백준 1697번 파이썬 문제풀이(BFS - 숨바꼭질)

---

위 문제는 해당 그래프만 이해하면 쉽게 풀 수 있는 문제이다.

즉, 예를들어 시작점이 5 이고 목적지가 17이라고 하자. 그렇다면 5에서 갈 수 있는 경우의 수 [-1,+1, *2] 를 계산한 4, 6, 10 이 존재한다.

이 값들은 1번만 이동한다면 갈 수 있기 때문에 전에값 0에서 +1을 한 1을 저장해 놓는다. 그 후에 각각 4에서 [3,5,8], 6에서 [5,7,12], 10에서 [9,11,20] 를 갈 수 있기 때문에 그 전에 저장되어있는 1에서 추가로 1번만 더하면 갈 수 있기 때문에 2를 저장한다.

이런 식으로 하다 보면 목적지 값 17에 저장하는 횟수가 나오게 될 것이다.

 

단! 여기서 주의해야할 점이 있다. 예를 들어 현재 4에는 1이 저장되어 있다. 그러나 위의 트리에서 보면 4는 계속 또나오게 된다.

 

값을 덮어 쓰게 되면 어떻게 될까? 그렇다면 값들은 꼬이게 된다. 꼬이게 되는 것은 크게 상관이 없다고 할 지라도(어차피 만약 목적지가 4라면 처음 2번째 트리에서 4가 나왔을때 bfs는 더 돌지않고 끝나게 된다.) 이미 방문했던 4를 또 방문하기 때문에 만약 위의 트리가 조금이라도 더 커지게 된다면 시간초과가 발생한다.

따라서 이것을 해결할 수 있는 방법은 초기에 설정할때 모든 그래프의 좌표 값을 0으로 초기화 한 후 아직 방문하지 않은 값(즉, 좌표에 저장되어 있는 값이 0인 좌표들)만 방문하여 값을 업데이트 할 수 있도록 한다. (위의 경우 4, 6, 10은 이미 방문했고 값을 1로 저장했기 때문에 더이상 방문하지 않도록 if를 걸어준다.)

 

import sys
from collections import deque


# input = sys.stdin.readline


def bfs(startx, destx):  # 시작점 , 목적지 좌표
    queue = deque()
    queue.append(startx)  # 큐에 시작점 추가

    while queue:
        x = queue.popleft()  # 맨 왼쪽(들어간순서대로) 좌표 하나를 뺀다.

        if x == destx:  # 만약 그 좌표가 목적지 좌표라면
            return graph[x]  # 그 좌표에 저장되어 있는 값을 리턴

        for i in range(3):  # 좌표를 이동할 반복문
            if i != 2:  # 만약 i가 2가 아니라면
                nx = x + dx[i]  # -1,+1
            else:  # 만약 i가 2라면
                nx = x * dx[i]  # *2

            if nx < 0 or nx >= len(graph):  # 만약 그래프가 좌표를 벗어난다면
                continue  # 밑의 함수 실행x

            if graph[nx] == 0:  # 만약 그래프값이 0이면(즉, 아직 방문하지 않았다면)
                queue.append(nx)  # 그 좌표를 큐에 추가하고
                graph[nx] = graph[x] + 1  # 좌표에 그 전에 좌표에 저장되어 있는 값에서 +1 한다.


graph = [0] * 100001  # 그래프 최대크기로 초기화
dx = [-1, 1, 2]  # 한번에 이동 할 수 있는 좌표 설정

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