[알고리즘] 백준1697 숨바꼭질 - 파이썬

오늘은 단계별로 풀어보기 'bfs와 dfs' 파트 중 7번째 문제입니다. 앞으로 세문제 정도 남았는데 시험기간이 끝나면 하루 두 세 문제씩 해서 모든 파트를 빨리 끝내고 싶습니다.

 

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

1697번: 숨바꼭질

 

 

풀이코드

# 예시 5 - 10 - 9 - 18 - 17
# 가장 빠른 시간을 출력하기 => 가장 빠른 거리를 찾는 문제와 유사하다고 생각 => bfs문제
from collections import deque
from sys import stdin

n, k = map(int, stdin.readline().split())
MAX = 10 ** 5 # 범위를 지정
graph = [0] * (MAX+1)


def bfs():
    queue = deque()
    queue.append(n)
    while queue:
        x = queue.popleft()
        if x == k: # 수빈이가 동생을 찾을 경우 결과 '초' 출력
            print(graph[x])
            break
        for dx in [x-1, x+1, x*2]: # 이동할 수 있는 세가지 경우
            if 0 <= dx < MAX and graph[dx] == 0:
                graph[dx] = graph[x] + 1 # 1초씩 증가
                queue.append(dx)

bfs()

 

문제풀이

: 이번 문제는 늘 풀었던 2차원 배열이 아닌 1차원 배열만 활용해서 처음에 어떻게 풀지 막혔던 문제였습니다. 풀이 코드는 전문제들 풀이와 크게 다를 바가 없었지만 직접 MAX값으로 범위를 만들어줘야 하는 점과 이동할 수 있는 세 가지의 경우(x-1, x+1, x*2)에 대허서 어떤 식으로 접근할지가 막혔던 문제였습니다.