[python] 백준 1697 : 숨바꼭질

[python] 백준 1697 : 숨바꼭질

1697번: 숨바꼭질 (acmicpc.net)

1697번: 숨바꼭질

실버 1

그래프, BFS

---

접근 

일차원으로 이동할 수 있는 bfs문제이다.

5를 노드라고 생각했을 때, 5가 탐색할 수 있는 노드는 4, 6, 10이된다.

각각의 노드는 [3, 5, 8], [5, 7, 12], [9, 11, 20]을 탐색할 수 있을 것이다.

 

여기서 미리 방문했던 노드는 방문하지 않도록 해야하며 노드가 일차원 이동을 하기 때문에 문제에서 주어진 범위를 벗어나지 않도록 해야한다.

 

노드는 값을 이동하면서 부모노드 방문횟수 + 1을 해주어야 한다.

 

문제 조건에서 N, K의 범위가 100000까지 였으므로, 방문할 노드가 1~100000까지의 범위를 넘지 않아야 접근할 수 있도록 조건을 걸어줘야 한다.

 

좌표평면을 1씩 움직이는 bfs문제와 상당히 유사한 부분이 많다.

 

코드

import sys; input = sys.stdin.readline
from collections import deque

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

N, K = map(int, input().split())
MAX = 100000
visited = [0] * (MAX+1)
bfs(N)

 

for문 범위를 for i in (q-1, q+1, 2*q)로 설정하면 노드가 탐색할 수 있는 3가지 노드를 순회할 수 있다.

for i in (q-1, q+1, 2*q):
            if  0 <= i <= MAX and not visited[i]:
                queue.append(i)
                visited[i] = visited[q] + 1

처음에 if not visited[i] and 0 <= i <= MAX: 로 작성했더니 큰 값을 입력했을때 계속 인덱스 에러가 발생했다.

 

파이썬은 if a and b 일 때 a가 false이면 b를 계산하지 않는다.

여기서 i는 q-1, q+1, 2*q 중에 하나이고 visitied[i]부분이 먼저 오면 인덱스를 벗어나면서 에러가 발생할 수 있지만, 0<=i<=Max가 먼저 오면 에러가 발생하지 않을 때만 visited[i]를 계산하기 때문에 문제가 생기지 않는다.