[백준 1697] 숨바꼭질

🍎 [백준 1697] 숨바꼭질

 

문제링크

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

 

⚾ 코드

from collections import deque

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

visited = [False for _ in range(200001)] # visited = False or True

dx = [1, -1, 2] # move

result = 0

q = deque()

# start
visited[N] = True

q.append([N, 0])

while q:
    x, count = q.popleft()

    if x == K: # if subin and her sister equal, break
        result = count
        break

    for i in range(3):
        if i != 2:
            nx = x+dx[i]
        else:
            nx = x*dx[i]

        if nx >= 0 and nx <= 200000 and visited[nx] == False:
            visited[nx] = True
            q.append([nx, count+1])

print(result)

 

🔔 해결 과정 & 깨달은 점

- BFS 알고리즘 방식을 써서 풀었다. 그 이유는 DFS/BFS문제 모음 안에 있어서 였기 때문이었는데, 아마도 그 힌트가 없었더라면 생각해내지 못했을 것 같다.

- 범위를 체크해 주는 부분은 조건문에서 가장 먼저 와야 한다! 그렇지 않으면 index out of range 에러가 난다.