1697

날짜 : 2022. 11. 04

사용 언어 : python

 

문제

 

 

코드

import sys
from collections import deque

n, k = map(int, sys.stdin.readline().split()) # 출발지, 도착지
visited = [False] * (100001)
q = deque()
visited[n] = True
visited[k] = True

def bfs(node):
    q.append([node, 0])
    while q:
        tmp = q.popleft()
        a = tmp[0] - 1 # -1
        b = tmp[0] + 1 # +1
        c = tmp[0] * 2 # * 2
        time = tmp[1] + 1 # 탐색 경과시간
        if a == k or b == k or c == k: # 원하는 위치에 있는 경우
            print(time) # 출력 후 종료
            exit(0)
        if a in range(0, 100001) and visited[a] == False: # 범위 파악 후 방문여부 확인
            visited[a] = True # 방문처리 후 push
            q.append([a, time])
        if b in range(0, 100001) and visited[b] == False:
            visited[b] = True
            q.append([b, time])
        if c in range(0, 100001) and visited[c] == False:
            visited[c] = True
            q.append([c, time])
    return
if n == k: # 이동할 필요가 없는 경우
    print(0)
    exit(0)
bfs(n)

 

 

알게된 점

- 처음 힌트만 보고 문제를 풀때 아무 생각이 안들었다. 이걸 어떤 방식으로 해야하나 싶었다.

- 그래서 태블릿에 직접 그려보니 그래프 형태가 나왔고 하나의 노드당 -1, +1, *2의 세 가지 자식노드를 만들 수 있고 이를통해 bfs를 전개하면 될 것이라고 생각했다.

- 또한 중복을 막기 위해 100001 크기의 리스트를 만들어 방문처리를 했다.

- 마지막에 이동할 필요가 없는 케이스를 간과하긴 했지만 직접 그려가면서 문제를 푸니까 나름(?) 수월하게 해결할 수 있었다.

 

 

참고 사이트

-