백준 13549 숨바꼭질3

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

 

 이 문제는 누나가 동생을 찾을 때 지금 위치에서 2배로 순간이동하면 0초, +-1로 이동하면 1초 걸려서 하나씩 탐색을 한다. 이때 동생을 찾는 가장 빠른 시간을 구하는것이 문제이다.

 

 이 문제는 언뜻보면 그냥 보통의 BFS로 풀어야하거나, 다익스트라 알고리즘으로 풀어야 할 것처럼 보인다. 그런 식으로 풀어도 괜찮지만 문제의 의도는 0-1 너비우선탐색 방법을 쓰는 것이 의도이기에 0-1 너비우선탐색을 알아보자.

 

 0-1 너비우선 탐색이란 그래프에서 모든 노드 사이의 엣지의 웨이트가 0혹은 1로 이루어져 있을 때 사용할 수 있다. 이 알고리즘의 작동을 간편히 설명하면, 일단 거리를 저장할 배열 뭐 dist를 정의한다. 그리고 우리가 통상의 bfs를 할 때에는 큐를 이용하여 구하지만 이 경우 우리는 엣지의 가중치가 0일때와 1일때의 처리우선도를 다르게 처리해야 한다. 일종의 우선순위 큐를 써야한다. 이 알고리즘은 0과 1의 순서만 고려하면 되므로 앞뒤에서 넣다 뺄 수 있는 덱을 사용한다. 배열과 덱을 정의했다면 이제 알고리즘을 돌려볼 수 있다. 알고리즘은 아래와 같이 돌아간다.

 

1. 덱의 앞에서 pop을 받는다

2. 이 pop의 간선을 조사해 이 pop에 이어져 있는 노드들의 거리를 최솟값으로 갱신한다.

3. 다음 노드까지의 가중치가 0이면 우선빼야 하기에 덱의 앞에 넣고, 1이면 나중에 빼야 하기에 덱의 뒤에 넣는다

4. 덱이 없어지거나, 원하는 값이 나올 때까지 반복한다

 

 이 때 우리가 엣지의 웨이트가 0인 경우를 앞에 넣는 것을 더 자세히 설명하자면, 가중치가 0이면 거리도 다 같기에, 먼저 최소부터 조지고 0인걸 다 구하고, 가중치가 1인 간선을 넘어가 거리가 1인걸 다 조지고, 그 다음 또 가중치가 1인 간선을 넘어가 거리가 2인걸 조지고,,,, 하는 식이다. 이렇게 최솟값부터 차레대로 조진다면, 이미 한번 지나간 길은 또 볼 일이 없게 된다. 이를 일종의 그림으로 표현하면

이런 식으로 1과 거리가 0인 층위(level), 가중치가 1인 간선을 넘어 거리가 1인 층위, 또 넘어 거리가 2인 층위인 식으로 나눠진다고 생각할 수 있다. 이때 같은 층위, 즉 가중치가 0인 것들부터 다 검사하고 간선 1을 넘어가면 층위를 차례대로 검사하게 되어 최솟값을 구할 수 있다. 그렇기에 덱을 이용하여 0을 앞에, 1을 뒤에 넣는다.

 

이제 문제로 돌아와 위의 알고리즘을 그대로 구현하면 풀 수 있다.

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

start,end = map(int,input().split())

limit = 100001
dist = [0]*limit

def bfs(start,end):
    deq = deque()
    if start==0:
        deq.append(1)
    else:
        deq.appendleft(start)


    while deq:
        cur_node=deq.popleft()
        if cur_node==end:
            return dist[cur_node]

        for next_node in [cur_node-1,cur_node+1,cur_node*2]:
            if 0<=next_node<limit and dist[next_node]==0:
                if next_node == cur_node*2:
                    dist[next_node] = dist[cur_node]
                    deq.appendleft(next_node)
                else:
                    dist[next_node] = dist[cur_node] + 1
                    deq.append(next_node)

if start==0:#엣지케이스
    if end==0:
        print(0)
    else:
        print(bfs(start,end)+1)

else:
    print(bfs(start,end))

 

이 문제의 경우 엣지케이스들도 여러개 있고, 검사를 할 때 작은 순서대로 안 넣고 무작위로 넣으면 순서가 꼬이는지 제대로 안 풀리기에, 작은 순서대로 넣어야한다.