[python] 백준 1697번: 숨바꼭질(BFS)

# 1697 숨바꼭

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

1697번: 숨바꼭질

⭐ 코드

import sys
input = sys.stdin.readline

from collections import deque
N, K = map(int, input().split())
MAX = 100001
visited = [-1] * MAX
visited[N] = 0 # 수빈이의 위치 방문처리
queue = deque()
queue.append(N)

if N > K: # K = 5, N = 17
    print(N - K)

else:
    while queue:
        x = queue.popleft()
        if x == K:
            print(visited[x])
            break
        
        for j in (x - 1), (x + 1), (x * 2):
            if 0 <= j < MAX and visited[j] == -1:
                visited[j] = visited[x] + 1 # 시간 기록
                queue.append(j)

📝 풀이

수빈이의 현재 위치에서 걷거나 순간이동을 해서 동생의 위치에 도달하도록 코드를 구현하면 된다. 이동을 하는데에는 1초의 시간이 걸리고 x-1, x+1, x*2의 연산 방법으로 이동할 수 있다. 가장 빠른 시간(적은 시간) 으로 동생의 위치를 찾아야하므로 BFS를 사용했다.

🔓 정답 코드 뜯어보기

from collections import deque
N, K = map(int, input().split())
MAX = 100001
visited = [-1] * MAX
visited[N] = 0 # 수빈이의 위치 방문처리
queue = deque()
queue.append(N)

수빈이와 동생의 위치 값을 각각 N과 K에 저장하고 범위 설정을 위해 MAX에 100001을 저장해준다. 방문처리를 위해 범위만큼 visited를 생성해주고, 처음 수빈이의 위치 visited[N]을 0으로 설정해 방문처리해준다.

# 수빈이가 더 큰 곳에 있다면 곱하기 연산과 더하기 연산은 불필요
if N > K: # K = 5, N = 17
    print(N - K)

else:
    while queue:
        x = queue.popleft()
        if x == K:
            print(visited[x])
            break
        
        for j in (x - 1), (x + 1), (x * 2):
            if 0 <= j < MAX and visited[j] == -1:
                visited[j] = visited[x] + 1 # 시간 기록
                queue.append(j)

만약에 수빈이의 위치가 동생의 위치보다 더 큰 값일 경우에는 x-1, x+1, x*2의 연산 중에서 x-1의 연산밖에 사용할 수 없다. 그렇기 때문에 바로 N - K를 통해 값을 출력해준다.

 

아닐경우에는 queue가 빌 때까지 반복문을 실행하고 x에 위치값을 할당시켜준다. 만약에 그 위치가 동생의 위치랑 같다면 (x == K) 그 위치까지의 걸린 시간을 출력해준다(visited[x])

 

수빈이가 동생에게 갈 수 있는 3가지 연산을 j에 넣어주면서 범위내에 있고 방문하지 않았다면 visited[j] = visited[x] + 1로직을 실행시켜준다. 로직을 좀 더 상세하게 살펴보면, 수빈이가 3가지 방법으로 간 위치(visited[j])에 +1을 하면서 시간을 기록해준다. 그리고 나서 이동한 위치(j)를 queue에 삽입시켜준다. 위와 같은 로직을 계속해서 실행하다가 x와 K가 같은 값, 즉 수빈이가 동생과 같아지는 위치에서 걸린 시간을 출력해준다.