[BOJ] 13549번 : 숨바꼭질 3(BFS, Dijkstra)

접근

대표적인 0-1 BFS 문제. 또는 다익스트라로 해결할 수 있다.

0-1 BFS 문제

• 노드간의 간선이 0 또는 1인 그래프를 탐색하기 위해 사용하는 BFS 문제.
• 일반적인 BFS문제와 큰 차이점은 없지만, 간선의 가중치가 0이 존재하기 때문에, 일반 BFS로 풀면 최단거리가 보장이 되지 않을 수 있는 문제가 발생.

위와 같은 0-1 BFS의 예시로 느낌이 올 수도 있겠지만, 최단거리를 보장하기 위해서 BFS를 살짝 변형한 것이다.

해결

우리가 사용하는 일반적인 BFS를 의사 코드로 작성해보겠다.

Queue = [시작 노드]
distance = [inf, inf, inf, ..., inf] # 거리를 무한대로 초기화 해두면, 방문 체크를 위한 리스트 대신 사용 가능
distnace[시작 노드] = 0

while Queue:
	방문 노드 = Queue.popleft()
    
    for 탐색 노드 in 간선[방문 노드]:
    	if distance[탐색 노드] == inf:
        	distance[탐색 노드] = distance[방문 노드] + 1
           	Queue.append(탐색 노드)

 

일반적인 BFS는 FIFO구조를 따르면서, 먼저 방문이 되어있다면 최단 거리임을 보장하기 때문에 최단 거리 탐색에 유용하게 사용된다. 그렇지만 BFS를 사용하는 상황은 간선들의 똑같은 가중치가 보장되어야한다. 하지만 이 문제는 이동시에 가중치가 0이 될 수도, 1이 될 수도 있다. 그래서 0-1 BFS라는 새로운 접근을 수행한다.

차이점은 크게 없지만, 탐색 노드 중 가중치를 0으로 사용해야하는 노드를 Queue에 가장 먼저 다시 넣어준다. 그렇게 되면, 다음 탐색 수행 시에 해당 노드를 먼저 방문한다는 보장이 되기 때문이다. 또한 가중치 0인 노드의 탐색을 항상 최우선으로 하기 위해, 가중치 1인 애들보다도 먼저 탐색을 진행하자.

Queue = [시작 노드]
edges = N x N 의 인접 행렬이든, 간선의 가중치를 저장해두기 위해서 필요
distance = [inf, inf, inf, ..., inf] # 거리를 무한대로 초기화 해두면, 방문 체크를 위한 리스트 대신 사용 가능
distnace[시작 노드] = 0

while Queue:
	방문 노드 = Queue.popleft()
    
    for 탐색 노드 in 간선[방문 노드]:
    	if distance[탐색 노드] == inf:
            if edges[방문 노드][탐색 노드] == 0:
                distance[탐색 노드] = distance[방문 노드] + edge[방문 노드][탐색 노드]
                Queue.appendleft(탐색 노드)
            elif edges[방문 노드][탐색 노드] == 1:
            	distance[탐색 노드] = distance[방문 노드] + edge[방문 노드][탐색 노드]
                Queue.append(탐색 노드)

그래프는 굳이 그리지 않겠다. 내용 자체가 어려운건 아니라서, 이 정도로 이해하고 넘어가도 될 것 같다. 

또한 이 문제에서 주의점은 거리를 저장하기 위해서 리스트를 생성할 때 최대 위치 제한보다 2배를 생성해야한다. 왜냐하면 위치의 제한은 정해져 있지만, 최대 거리가 어디까지인지는 정해져있지 않기에, 2배를 갔다가 돌아오는 것이 최소거리가 되는 반례가 존재한다. 내가 그것때문에 틀렸다. 반례는 

$ N = 2, K = 7 $ 이라면,

2 -> 4 -> 8 -> 7 이런식으로 가는 경로가 존재한다.

일반적으로 BFS를 풀 땐, 용량 제한 때문에 나와있는 값 중에 가장 큰값까지만 체크하는 습관이 있기 때문에 해당 반례를 생각하지 못했다.

---

각설하고 다시 알고리즘으로 와보자.

0-1 BFS를 보면서, 또 뭔가 비슷한 알고리즘의 생각이 들지않았는가? 바로 Heap구조를 이용해서 가장 적은 값부터 체크하는 Dijkstra 알고리즘이 있다. Dijkstra 알고리즘은 최소가 되는 가중치를 방문하면서, 거리 그래프를 갱신해나가는데, 한번 이 문제에서의 예시로 보자.

N=5, K=17

갈 수 있는 경로 중 최단 거리를 포함한 일부만 그래프로 나타나보았다. 거리 테이블은 아래와 같이 초기화된다.

5	6	7	8	9	10	11	12	13	14	15	16	17
0	inf	inf	inf	inf	inf	inf	inf	inf	inf	inf	inf	inf

 

Dijkstra는 Heap구조를 이용해서, 가중치가 가장 작은 노드부터 방문한다는걸 명심하고, 갱신을 진행해보자.

처음에 heap에는 시작 노드인 N=5가 들어가 있다.

가장 먼저 heappop을 해주면, 5가 뽑히고 5와 연결된 노드는 4(5-1), 6(5+1), 10(5*2) 라고 볼 수 있다.

그럼 테이블은 아래와 같이 갱신되고, heap에는 갱신된 가중치를 포함해서 heappush를 해준다.

5	6	7	8	9	10	11	12	13	14	15	16	17
0	1	inf	inf	inf	0	inf	inf	inf	inf	inf	inf	inf

$ heap(가중치, 노드) = [(1, 6), (0, 10)] $ 순서는 무시하고, 힙구조를 따라서 pop과 push가 일어난다고 가정하는 것이다.

 

그럼 그 다음 heappop이 일어난다면, 파이썬 heapq의 우선순위대로 뽑히면, (0, 10)이 뽑힐 것이다.

그리고 갱신이 일어나면,

5	6	7	8	9	10	11	12	13	14	15	16	17
0	1	inf	inf	1	0	1	inf	inf	inf	inf	inf	inf

$ heap = [(1, 6), (0, 20), (1, 9), (1, 11)] $ 이런식으로 진행된다.

다익스트라는 방문을 했어도, 해당 노드의 값이 가중치를 더한 값보다 크다면 계속해서 갱신을 진행한다는 이점이 있기에, 이런식으로 가장 가중치가 적은 노드를 방문해가면서 갱신을 수행할 수 있다. 이런 이점으로 가중치를 계속 최소값으로 유지해나가며, 갱신해주면서 도착 노드까지 최솟값을 보장할 수 있는 것이다.

글로 작성하려니 말이 너무 길어지는 것 같아 두가지 방법의 코드를 모두 작성해두겠다. 시간제한이 비교적 널널해서, 최적화한 코드가 아니지만 두 코드 모두 다 통과된 방법이기에 참고해서 해결하면 좋을 것 같다.

코드

0-1 BFS

from collections import deque

N, K = map(int, input().split())

# 0-1 BFS
que = deque([N])
visited = [float('inf')] * (200_000+1) # 한계치의 2배로 지정해주자. 처음엔 N, K 중 큰값으로 했지만, 위치의 제한이 없기때문에 N=2, K=7 같은 경우엔 2 -> 4 -> 8 -> 7 이런 경로도 나올 수 있다.
visited[N] = 0

while que:
    v = que.popleft()
    
    if v == K:
        print(visited[v])
        break
    if 2 * v < 200_000+1 and visited[2*v] == float('inf'):
        visited[2*v] = visited[v]
        que.appendleft(2*v) # 가중치가 0에 해당된다면, deque에 가장 앞에 넣어서, 그 다음 순회 때 먼저 탐색할 수 있도록 한다.
    if v - 1 >= 0 and visited[v-1] == float('inf'):
        visited[v-1] = visited[v] + 1
        que.append(v-1)
    if v + 1 < 200_000 + 1 and visited[v+1] == float('inf'):
        visited[v+1] = visited[v] + 1
        que.append(v+1)

Dijkstra

import heapq

N, K = map(int, input().split())

# Dijkstra
visited = [float('inf')] * (200_000+1)
heap = []
heapq.heappush(heap, (0, N))
visited[N] = 0

while heap:
    w, v = heapq.heappop(heap)
    
    if v == K:
        print(visited[v])
        break
    
    if 2*v < 200_000+1:
        if visited[2*v] > visited[v]:
            visited[2*v] = visited[v]
            heapq.heappush(heap, (visited[2*v], 2*v))    
    if v-1 >= 0:
        if visited[v-1] > visited[v] + 1:
            visited[v-1] = visited[v] + 1
            heapq.heappush(heap, (visited[v-1], v-1))
    if v+1 < 200_000+1:
        if visited[v+1] > visited[v] + 1:
            visited[v+1] = visited[v] + 1
            heapq.heappush(heap, (visited[v+1], v+1))