[BOJ] 1697. 숨바꼭질

Python3

문제

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

키워드

• 그래프 탐색
• 너비 우선 탐색

문제 풀이

문제 요구사항

1. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다.
2. 수빈이의 위치가 X일 때, X-1 또는 X+1, 2*X의 위치로 이동하게 된다.
3. 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램

변수 및 함수 설명

• N: 수빈이 현재 점(출발점) (0 ≤ N ≤ 100,000)
• K: 동생 현재 점(목적지) (0 ≤ K ≤ 100,000)

• bfsQueue: bfs 탐색을 위한 큐
• visited: 방문 위치를 표시하는 리스트
• loc: 현재 위치
• nloc: 다음 위치

풀이

(입력 및 선언)

• 수빈이와 동생의 현재 위치(n, k)를 입력받는다.
• bfsQueue, visited를 선언한다 (최대 10만까지 가능)

(bfs)

• 큐에 원소가 있을 때까지 반복

  • 큐에 있는 첫 번째 원소를 현재 위치(loc)로 저장한다.
  • 만약 현재 위치가 동생이 위치한 곳(k)라면 현재 위치를 반환하고 종료한다.

  수빈이는 총 3가지 이동이 가능하다.
  1) 다음 위치가 (현재 위치 - 1)이다.
  2) 다음 위치가 (현재 위치 + 1)이다.
  3) 다음 위치가 (현재 위치 * 2)이다.

  이 중 하나이고, 방문하지 않은 곳이라면,
  1초 늘리고 큐에 해당 위치를 넣는다.

(함수 호출)

• 수빈이가 위치한 현재 위치(n)을 큐에 넣는다
• bfs 함수를 호출한다

최종 코드

from collections import deque

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

bfsQueue = deque()
MAX = 10 ** 5
visited = [0 for _ in range(MAX + 1)]

def bfs():    
    while bfsQueue:
        loc = bfsQueue.popleft()

        if loc == k:
            print(visited[loc])
            break

        for nloc in (loc - 1, loc + 1, loc * 2):
            if 0 <= nloc <= MAX and not visited[nloc]:
                visited[nloc] = visited[loc] + 1
                bfsQueue.append(nloc)

bfsQueue.append(n)
bfs()