[백준] 13549번 숨바꼭질 3(feat. 다익스트라, BFS)

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

 

문제 분석

• 첫 번째 단계 (문제 요약 및 조건 파악하기)

수빈이는 현재 점 N(0 <= N <= 100,000)에 있다.
동생은 점 K(0 <= K <= 100,000)에 있다.

수빈이는 이동을 할 수 있는데, 

위치가 X일 때 

• 걷는 경우 
  • 1초 후에 x - 1 or x + 1 위치로 이동
• 순간이동 하는 경우
  • 0초 후에 2 * x 위치로 이동

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

 

• 두 번째 단계 (문제의 핵심 파악하기)

이 문제는 가중치가 0 또는 1인 그래프로 생각할 수 있다.

0부터 10만까지의 노드가 있고, 모든 노드는 0이상 10만 이하의 범위 안에서 -1, +1, 2x의 노드와 간선으로 연결되어 있는 그래프이고, 간선의 가중치는 0또는 1이다. 가중치는 모두 0또는 양수이고, 특정 노드까지의 최단 경로 가중치를 구하는 것이므로 다익스트라 알고리즘을 적용할 수 있다.

기존의 다익스트라 형태에서 조금 다른 점은, 그래프 간선 정보가 따로 주어지는 것이 아니라, 
현재 노드에 대해 -1, +1, 2x를 인접노드로 정의하고 순회하면 된다. 이를 위해 제너레이터를 사용한다.

이 때 인접 노드 중 범위를 벗어나는 경우를 걸러줘야 한다.

 

코드 작성 (다익스트라 적용 풀이)

import sys
import heapq

INF = int(1e9)
n, k = map(int, sys.stdin.readline().rstrip().split())

# 인접 노드들을 iterable한 값으로 리턴하기 위한 제너레이터 함수
# 코드가 간단해짐
def move(x):
    yield (x - 1, 1)
    yield (x + 1, 1)
    yield (2 * x, 0)

# 다익스트라 알고리즘
def n_to_k(n, k):
    graph = [INF] * (100001)
    graph[n] = 0
    q = [(0, n)]

    while q:
        cnt_time, cnt_x = heapq.heappop(q)

        if cnt_time > graph[cnt_x]:
            continue

        # 0부터 100000까지의 모든 노드들은, 조건 범위 안에서
        # 자신의 -1, +1, *2 의 인접 노드를 가짐
        # 그래서 제너레이터를 통해 직접 인접 노드를 구하여 순회하면 됨
        for node_x, node_time in move(cnt_x):
            cal_time = cnt_time + node_time

            # 인접 노드로 구한 값이 조건 범위 안에 있어야 함
            if 0 <= node_x <= 100000 and cal_time < graph[node_x]:
                graph[node_x] = cal_time
                heapq.heappush(q, (cal_time, node_x))

    return graph[k]

print(n_to_k(n, k))

 

---

 

BFS를 이용한 다른 풀이

BFS는 인접 노드들을 너비 우선 탐색하면서 최단 경로를 찾는 알고리즘이다.

다만 이 문제는 0과 1의 가중치가 있는 그래프가 대상이기 때문에, BFS를 사용하려면 약간의 변형을 생각해봐야한다.

우선, BFS는 가중치가 없는 그래프에서 가장 먼저 목표 노드를 찾았을 때, 그 때까지의 경로가 최단 경로임이 보장된다.

이 문제에서 너비 우선 탐색했을 때 최단 경로임을 보장하려면, 그래프의 어떤 노드의 인접 노드를 탐색할 때의 가중치가 0인 노드부터 먼저 방문해야 한다.

서로 같은 level에 위치한 노드들 중에서, 가중치가 0인 노드는 가중치를 하나도 늘리지 않고 한 단계 진행할 수 있으므로, 같은 level의 다른 노드로 나아갔을 때와 비교하여 경로의 길이가 줄면 줄었지 최소한 더 늘어나지는 않게된다.

따라서 인접 노드를 탐색할 때 가중치가 0인 노드부터 우선 방문하도록 설계하면, BFS의 '이미 방문했던 노드는 방문하지 않고, 너비를 우선적으로 탐색하는 로직'대로 최단 경로를 찾을 수 있게 된다.

 

코드 작성(BFS 적용 풀이)

import sys
from collections import deque

n, k = map(int, sys.stdin.readline().rstrip().split())

# BFS는 한 번 방문한 노드는 다시 방문하지 않음
# 따라서 같은 level에 대하여 인접 노드로의
# 가중치가 0인 2 * x 부터 방문해야 함
def move(x):
    yield (2 * x, 0)
    yield (x - 1, 1)
    yield (x + 1, 1)

def BFS(start):
    graph = [-1] * (100001)
    graph[start] = 0
    q = deque([start])

    while q:
        cnt_x = q.popleft()

        if cnt_x == k:
            return graph[k]

        for node_x, node_time in move(cnt_x):
            cal_time = graph[cnt_x] + node_time
            if 0 <= node_x <= 100000 and graph[node_x] == -1:
                graph[node_x] = cal_time
                q.append(node_x)

print(BFS(n))

 

다익스트라와 BFS 개념 차이 확실히 알아둘 것.