[백준 파이썬] # 1697 숨바꼭질

Silver I

# 1697 숨바꼭질

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

1697번: 숨바꼭질

 

풀이

from collections import deque

def bfs(n, k):
    q = deque([n])
    while q:
        pop = q.popleft()
        if pop == k:
            return visited[pop]
        for i in [pop-1, pop+1, 2*pop]:
            if 0<=i<=MAX and not visited[i]:
                visited[i] = visited[pop] + 1
                q.append(i)
                
N, K = map(int, input().split())
MAX = 100000
visited = [0] * (MAX+1)

print(bfs(N, K))

 

풀이 방법

• bfs → 체커를 활용할 수 있다는 것을 생각해내자.
• visited 행렬에 몇번 과정을 거쳐 도착하는지를 기록한다.
• [0]은 [False]의 의미를 갖는다. visited를 만들 때 0을 이용해 만들수 있고, not visited[i]를 사용할 수 있었던 이유이다.
• 이유를 정확하게는 모르겠다. visited = [0] * MAX 를 시도 했을 때 런타임 오류가 나는데, [0] * (MAX+1)로 해주면 런타임 오류를 해결할 수 있었다. 왜 꼭 그래야 하는지 명쾌하지가 않다.

 

후기

• bfs 문제 풀 때 어떤 방식이든 체커를 활용, q.append 과정이 필요하단 걸 염두해두자.
• 체커는 1) 그래프에 직접 입력하는 방법 2) visited 행렬을 만들어 활용하는 방법이 있다.
• 트리 구조로 노트를 그려 풀이하는 방식은 풀이 과정에 Good
• 문제풀이가 암기과정이 되면 안될텐데 하는 우려가 조금.. ㅎㅎ 있다.

cf. 이해되지 않는 부분.. 아래 코드는 i 리스트만 다른건데 왜 틀렸다고 채점되는지 모르겠다

from collections import deque

def bfs(n, k):
    q = deque([n])
    while q:
        pop = q.popleft()
        if pop == k:
            return visited[pop]
        for i in [2*pop, pop-1, pop+1]:
            if 0<=i<=MAX and not visited[i]:
                visited[i] = visited[pop] + 1
                q.append(i)
                
N, K = map(int, input().split())
MAX = 100000
visited = [0] * (MAX+1)

print(bfs(N, K))