[백준/Python] 1697번 숨바꼭질

문제

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

---

문제 풀이(정답)

from collections import deque

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

visited = [0] * 100001

def bfs():

    q = deque()

    q.append(n)

    while q:

        x = q.popleft()

        if x == k:

            print(visited[x])

            break

        for j in (x-1, x+1, 2*x):

            if 0 <= j <= 100000 and not visited[j]:

                visited[j] = visited[x] + 1

                q.append(j)

bfs()

 

이 문제는 너비우선탐색(BFS)를 이용해서 풀었다.

먼저 시작위치 n과 도착위치 k를 받아준 후, 각 위치까지 도달하는 최소 시간을 visited 변수에 저장해줍니다.

visited변수의 길이는 문제 조건에 N(0 ≤ N ≤ 100,000) 라 정해져있다.

 

그리고 어제 개념을 정리했던 너비우선탐색 함수를 작성했다.

너비 우선 탐색은 큐를 이용해 알고리즘을 구현한다.

 

먼저 시작 위치를 큐에 추가해 준다.

그리고 조건문을 활용해 현재 위치와 도착 위치가 같다면 반복문을 종료해주는 코드를 작성한다.

 

그렇지 않으면 수빈이가 이동할 수 있는 경로를 이용해 코드를 작성 해 주었다.

수빈이가 이동할 수 있는 경로
1. x-1 : 한 칸 뒤로 이동
2. x+1 : 한 칸 앞으로 이동
3. x*2 : 순간 이동

 

범위를 벗어나지 않고 방문하지 않은 경우, 이동시간을 갱신하고 j를 큐에 추가해준다.

---

런타임에러(IndexError)

코드를 제출했더니 런타임에러가 나서 왜 에러가 나지..? 생각했다.

if 0 <= j <= 100000 and not visited[j]:

 

알고 보니 조건의 순서도 굉장히 중요했다.

나는 not visited[j]의 조건을 먼저 작성하였는데 이렇게 작성을 하면 j가 범위를 벗어난 값을 조회할 때 IndexError 발생이 가능하다.

 

해결 방법
✅ 0 <= j <= 100000를 먼저 체크한 후 visited[j]의 방문 여부를 확인한다.