백준 1697 숨바꼭질 파이썬 풀이

와 대박이다

이거 풀이의 핵심 알고리즘이 뭔지 아세여????놀랍게도 bfs임 와이파이 모양으로 확장하는거

왠지모르게 bfs는 와이파이 모양이 떠오른다.. 그리고 그렇게 생각하면 쉽게 이해된다)

 

자자 암튼 코드는 이렇다

# 1697
from collections import deque

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

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

def bfs():
    q = deque()
    q.append(N)
    while q:
        x = q.popleft()
        if x == K:
            print(dist[x])
            break
        for nx in (x-1, x+1, x*2):
            if 0 <= nx <= MAX and not dist[nx]: # not visited node 
                dist[nx] = dist[x] + 1 # 1초 소요된다
                q.append(nx) # 방문표시한 노드를 큐에 삽입한다

bfs()

 

이문제를 접하고 난 생각은 : bfs를 이렇게 유용하게 활용하는가 ?!?! 대박이다 코테에 자주 내는 이유가 있다

N에서 이동하는 방법은 총 3가지이다

N+1, N-1, N*2 

그리고 이걸 N == 5인경우로 생각해봤을 때, 아래 그림이랑 같다. 어 그리고 이 방법으로 하면 대강 시간 초과는 안나겠거니 예상했다 연산을 하게 되면 O(3**N) 이겠지 이걸 MAX = 10**5 라고 제한해둔다 !

 

이거이거 이 그래프를 그렸으면서 bfs를 바로 떠올리지 못했다 근데 이건 그래프 자료구조이고 bfs 방식으로 쭉쭉 확장해나가면서 각각의 노드들을 탐색할 수 있다 우왕굿 ㅎㅎ

 

저 위에 그림을 90도 회전하면 우리가 생각하는 전형적인 그래프 모양인데 ㅠㅠ 이렇게 돌려놓고 보니 오오 bfs 탐색 사용할 수 있겠구나 싶었고 알고리즘도 사실 저게 다임 

 

bfs 가 dfs랑 다른점은? queue를 사용한다 자동반사적으로 나오잖아여..^^

그래서 거리를 저장해둘 dist 배열을 0으로 초기화시켜서 만들어 줬슴당

dist = [0]*(MAX+1)

또 queue에 담아놓고 하나씩 popleft (맨 앞쪽에 있는 노드부터 빼는거 아시져?!) 시키고, x = q.popleft()

현재의 x 지점에서 인접한, 탐색되지 않은 노드들을 큐에 넣어주어야져 !!!! 

탐색되지 않은 노드들은 0 이 저장되어 있을 것이므로 not dist[nx] 라고 조건을 걸어주었습니다 참고로 0 이 false이니까.. 파이썬은 참 편리하다

q.append(nx) 해서 큐에 방문되지 않은 노드들을 삽입합니당

    while q:
        x = q.popleft()
        if x == K:
            print(dist[x])
            break
        for nx in (x-1, x+1, x*2):
            if 0 <= nx <= MAX and not dist[nx]: # not visited node
                dist[nx] = dist[x] + 1 # 1초 소요된다
                q.append(nx) # 방문표시한 노드를 큐에 삽입한다

 근데 우리의 궁극적인 목적은 그래서 N이 K 위치로 이동하는데 걸리는 시간을 구하는거고 한번 이동이 있을 때마다 1초 소요되니까

dist[nx] = dist[x] + 1 

이렇게 1초씩 더해주는 것이지여... 근데 왜 dist[x] 이겠습니까 이전 지점의 기준에서 '여기까지 오는데 소요된 시간'을 저장해 두었기 때문이죠

BFS 기억하자 !!