[백준] 1697 - 숨바꼭질

from collections import deque

n, k = map(int, input().split())

# 하나씩 끝까지 파볼(dfs) 필요 없이, 가까운 노드부터 확인하다가
# 종착점 도착하면 끝내면 되므로 BFS!!
def bfs():
    que = deque()
    que.append(n)
    while que:
        x=que.popleft()
        if x==k:
            print(dist[x])
            break
        for nx in (x-1,x+1,x*2):
            # dist[nx]=0(False)이어야 아래가 참이 됨.(이유:재방문 못하게)
            if 0<=nx<=10**5 and not dist[nx]:
                # 첫 시작 노드에서부터 퍼져나가는 노드에
                # +1씩 해주면서 연산횟수 표시함
                # 그러다가 n=k되는 순간오면 바로 멈추면 되니까
                # 다시 방문할 수 없도록 if문에 and not dist[nx]
                # (그래서 BFS 방식을 사용하는 거기도 하고)
                dist[nx]=dist[x]+1
                q.append(nx)

dist = [0]*(10**5+1)

bfs()

• 풀이 평가 : 1시간 정도 고민했는데 못풀었다ㅠㅠ
• 풀이 핵심 아이디어 :
  • DFS가 아닌 BFS 사용!!! (따라서 queue 사용)
    ⇒ 하나씩 끝까지 파볼(dfs) 필요 없이, 가까운 노드부터 확인하다가 종착점 도착하면 끝내면 되므로 BFS!!
  • 도달할 수 있는 모든 거리(0~100,000)로 리스트 세운 후, 방문 순서를 표시해준다!
    ⇒ 추가 설명 : 첫 시작 노드에서부터 퍼져나가는 노드에 +1씩 해주면서 연산횟수 표시하다가, n=k되는 순간오면 바로 멈춘다는 소리
    ⇒ 이때 방문 순서란, 제일 상위 노드는 1, 그 다음 가지 노드들은 2, 이런식으로... 그러다 k에 도달하면 break 되어서 결과값 출력하게 함.
  • 재방문 막기 위한 장치 : if문에 and not nx(현재노드에 대한 위치 표시 리스트)으로 거른다