1 분 소요

[Silver I] 숨바꼭질 - 1697

문제 링크

성능 요약

메모리: 34972 KB, 시간: 100 ms

분류

너비 우선 탐색, 그래프 이론, 그래프 탐색

제출 일자

2024년 4월 3일 12:07:22

문제 설명

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다.

수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오.

입력

첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다.

출력

수빈이가 동생을 찾는 가장 빠른 시간을 출력한다.

풀이

dp를 이용해서 풀어야 할 문제라고 생각했지만, 그래프탐색을 이용하는 문제였다. 기본적인 BFS 코드에서 수정하면 되는데 어떤 흐름으로 가져가야 될지 감을 못잡았다. 그래서 이해하기 쉽게 그림으로 표현해보았다.

이동할 수 있는 방법은 총 3가지이다.

  1. N - 1 : 뒤로 1칸
  2. N + 1 : 앞으로 1칸
  3. N * 2 : 현위치값의 2배 앞으로
시간으로 나뉘어진 각 층을 모두 탐색하고 다음 시간으로 넘어가는 방식이 너비우선탐색을 하는 과정이다. 이동할 때마다 1초씩 소요가 되고 모든 경우의 수가 계산되므로 동생의 위치를 찾은 그 시점에서의 시간이 가장 빠른 시간이 된다.

전체 코드

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

N, K = map(int, input().split())
visit = [0]*100001 # 최대 100000크기의 방문 리스트 초기화

def BFS(n):
    q = deque() # 시작점을 지정하는 deque선언
    q.append(n) # 수빈이의 위치 추가

    while q: # 탐색할 위치가 없을 때까지
        c = q.popleft() # 시작점을 꺼내서 c에 저장
        if c == K: # 수빈이가 동생을 찾았으면
            return visit[K] # 동생위치 도달 최소시간 반환
        for i in (c+1, c-1, c*2): # 앞으로 1칸, 뒤로 1칸, 2배로 이동
            if 0<= i <100001 and not visit[i]: # i가 문제에서의 수 범위를 만족하고, 아직 i를 방문하지 않았다면,
                visit[i] = visit[c] + 1 # 방문과 동시에 이전위치까지의 소요시간에 + 1초
                q.append(i) # 탐색할 시작점에 i 추가

print(BFS(N))

댓글남기기

참고