[백준 - Python] 1697번 : 숨바꼭질

 

 

🌱   문제

 

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

1697번: 숨바꼭질

 

💡   설명

해당 문제는 BFS(너비 우선 탐색) 알고리즘으로 해결할 수 있는 문제입니다.

만약, BFS가 아닌 DFS(깊이 우선 탐색)를 사용하여 문제를 해결하려고 하면 시간초과가 발생합니다.

해당 문제에서 BFS와 DFS 사용의 차이를 생각해본 결과는 다음과 같습니다.

 

DFS는 찾고자 하는 방향에 노드가 있으면 매우 빠른 속도로 찾을 수 있으나, 반대로 찾고자 하는 방향에 노드가 없다면 많은 오버헤드가 발생합니다.

예를 들어, 해당 문제에서 동생은 맨 앞(1)에 있는데, 동생 보다 한 칸 앞에 위치한 형(2)이 우선 한 칸씩 앞으로 이동하며 탐색하도록 설계했다면 범위 내에서 반복적으로 한 칸씩만 뒤로 이동하여 시간초과가 발생합니다.

ex. 동생 위치 : 1  /  형 위치 : 2

1[동생] / 2[형 탐색]  ->  (2, 3 ,4 , 5, ... , 99999, 100000)

 

즉, 해가 없는 경로에서 깊이 빠질 위험이 존재합니다.

 

반면, BFS는 현재 위치에서 그물망처럼 -1, +1, x2 만큼 퍼져나가며 최적의 해를 찾기 때문에 안정적인 시간 내에 정답을 찾을 수 있습니다.

따라서 최적의해를 보장받고자 하는 경우에는 BFS를 사용하는 것이 유리합니다.

 

✏️   소스코드

#-*- coding:utf-8 -*-
from collections import deque
import sys

input = sys.stdin.readline
MIS = lambda: map(int, input().rstrip().split())

start, dest = MIS()
res = sys.maxsize


def f(start, dest):
    visited = [False] * 100001
    q = deque([(start, 0)])
    result = sys.maxsize

    while q:
        now, count = q.popleft()
        
        if not (0 <= now <= 100000): continue
        if visited[now]: continue
        visited[now] = True

        if now == dest:
            result = min(result, count)

        q.append((now+1, count+1))
        q.append((now-1, count+1))
        q.append((now*2, count+1))

    return result

print(f(start, dest))

 

 

 

github : https://github.com/tmdgh1592

tmdgh1592 - Overview