[백준 문제풀이] 1697번 : 숨바꼭질

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

1697번: 숨바꼭질

💡 아직도 dfs bfs 바로 구현 못해서 개념 다시 확인하고 문제 푸는 중. 특히 bfs보다는 dfs를 더 많이써서 bfs는 어색하다. 

 

bfs는 너비우선탐색으로 하나의 노드를 확인하면 해당노드에 연결된 다른 노드를 큐에 넣고 순서대로 꺼내면서 전체를 확인하는 방식이다. 보통 deque를 사용하여 leftpop()을 하고, visited를 활용해 원하는 값을 저장한다. 

 

이 문제의 경우 visited는 해당 노드를 방문했는지를 확인함과 동시에 몇초가 걸렸는지도 확인할 수 있다.

 

✔소스코드

import sys
from collections import deque
N,K=map(int,sys.stdin.readline().split())
visited=[0]*100001

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