알고리즘/백준[baekjoon]

[baekjoon] 백준 1697번 : 숨박꼭질 (by python 파이썬) with bfs

코딩하는이씨 2022. 5. 8. 17:12
728x90
반응형

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

 

1697번: 숨바꼭질

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일

www.acmicpc.net

 

정답 code

from collections import deque

def bfs():
    queue = deque()
    queue.append(n)
    while queue:
        x = queue.popleft()
        if x == k:               #원하는 값일경우 출력후 탈출
            print(distance[x])
            break
        for i in (x-1,x+1,2*x):  #3가지 옵션 탐색
            if 0<= i <= max and not distance[i]:
                distance[i] = distance[x]+1
                queue.append(i)

        
n,k = map(int,input().split())
max = 10 ** 5
distance = [0] * (max+1)
bfs()

이번 문제는 최단 시간을 구하는 문제로 너비 우선 탐색 (bfs)를  활용한 문제이다.

 

solution

주어진 입력을 받고 해당 위치까지의 시간을 입력하기위한 distance 리스트를 만들어준다.

bfs함수를 만들어 deque를 생성한다.

while문에서 탐색을 시작하는데 큐속의 원하는 값이 나오면 출력하고 종료한다.

for 문에서 문제에서 원하는 3가지 옵션 (x-1 x+1 2*x)를 n에서부터 탐색해 최단시간을 distance에 기록후

queue에 추가한다.

 

728x90
반응형