BFS(너비 우선 탐색)

BFS는 DFS와 동일하게 컴포넌트의 모든 정점을 한 번씩 순회한다.

 

BFS는 이름에서도 알 수 있듯 깊이를 우선적으로 탐색하는 DFS와는 반대의 성향을 지닌다.

 

DFS가 한 방향으로 아래로 아래로 내려가다 끝을 찍고 다시 돌아와 그 방향으로 다시 아래로 탐색하는것과 달리 BFS는 모든곳을 똑같이 조금씩 탐색한다.

위 그림을 통해서 BFS를 해보자

 

맨처음 1번 정점을 방문하고 그 다음 단계는 자식 정점의 인접 정점을 우선적으로 탐색하던 DFS와 달리 부모 정점과 인접한 정점들을 우선적으로 탐색한다.

 

DFS였다면 1 → 2 → 5 → … 이런식으로 탐색 했겠지만 BFS는1과 인접한 정점들을 우선적으로 탐색한다.

 

따라서 순서는 다음과 같다.

1 → 2 → 3→ 4 → 5 → 6 → 7 → 8 → 9 → 10 → 11 → 12

 

여기서 0번 노드, 즉 시작점을 방문한 것을 0단계라 하고 그 다음부터 1, 2, 3단계라고 부를 때, k단계에 방문하는 정점들은 시작점으로부터 최단거리가 k이다.

 

최단거리라 함은, 여기서는 가중치도 없으니까 A와 B의 최단거리는 A에서 B로 이동하는 데 필요한 최소 개수의 간선이라고 보면된다.

 

BFS는 DFS와 대조적으로 큐를 사용한다.

 

DFS가 최근에(자식 정점) 방문한 노드들부터 보는것과 반대로 BFS는 먼저 방문(부모 정점)한 노드들 부터 보기 때문이다.

---

BFS는 잘 사용한다면 각 정점마다 시작 정점으로부터의 거리를 알아낼 수 있다! 문제를 통해 한 번 알아보자.

 

특정 거리의 도시 찾기

18352번: 특정 거리의 도시 찾기

18352번: 특정 거리의 도시 찾기

 

이 문제의 경우 특정 시작점으로 부터 거리가 K인 도시들을 찾아내는 문제이다.

 

위에서 BFS는 잘 사용한다면 시작 정점에서 특정 정점의 거리를 알아낼 수 있다고 했는데, 때문에 각 정점의 최단거리를 재야할 때 요긴하게 쓸 수 있다.

 

특정 거리의 도시 찾기

# 특정 거리의 도시 찾기
import sys
from collections import deque

n, m, k, x = map(int, sys.stdin.readline().split())
graph = [[] for _ in range(n+1)]
distance = [0] * (n+1)
for i in range(m):
    a, b = map(int, sys.stdin.readline().split())
    graph[a].append(b)

visited = [False] * (n+1)

def bfs(st):
    q = deque()
    q.append(st)
    visited[st] = True
    result = []
		# 시작 정점의 거리는 당연히 0이다.
    distance[st] = 0
    while q:
        val = q.popleft()
        for node in graph[val]:
            if not visited[node]:
                q.append(node)
                visited[node] = True

                # 인접 정점들은 pop한 정점의 레벨 아래에 존재하기에 + 1 해준다.
                # 시작점과 인접한 정점 아래에 있는 정점들의 거리도 알 수 있다.
                distance[node] = distance[val] + 1
                if distance[node] == k:
                    result.append(node)
    if len(result) == 0:
        print(-1)
    else:
        result.sort()
        for i in result:
            print(i)
bfs(x)

 

BFS가 자기와 인접한 정점을 먼저 탐색하기에 시작 정점에서의 깊이를 알 수 있다.

 

깊이가 내려갈 때마다 자기 깊이에서 +1하게되면 시작 정점에서 모든 정점으로의 거리를 알 수 있게 된다!

 

---

다음으로 동전 2 문제를 풀어보자

 

동전 2

2294번: 동전 2

2294번: 동전 2

주어진 동전들을 중복을 허용해서 그 가치가의 합이 K원이 되도록 하는 문제이다.

 

이 문제는 DP를 사용해서도 풀 수 있는데, 여기선 BFS를 사용해서 풀어보자.

 

기본으로 주어지는 동전들을 우선, 큐에 집어넣는다.

 

그리고 큐에서 동전을 꺼내 기본으로 주어진 동전 리스트에서 순차적으로 합해서 그 합을 만드는데 드는 동전 갯수와, 합을 다시 큐에 넣어준다.

 

이렇게 만들어진 동전은 중복적으로 만들어질 수 있는데, 15의 경우 12, 1, 1, 1 또는 5, 5, 5 … 등 존재한다.

 

때문에, 이미 만들어진 경우가 있다면 check 배열에다가 이미 만들어져있다고 체크한다.

 

사용되는 동전이 많을수록 큐의 뒤에 넣어짐으로 k에 해당하는 합을 찾고 바로 출력하면 그게 최소 갯수가 된다.

# 동전 2
import sys
from collections import deque
n, k = map(int, sys.stdin.readline().split())
coins = []
check=[False for _ in range(k+1)]
for _ in range(n):
    coin = int(sys.stdin.readline())
    coins.append(coin)
coins = list(set(coins))

def bfs():
    q = deque()
    for coin in coins:
        if coin < k:
            q.append((coin, 1))
            check[coin] = True
		# 큐에서 동전을 뽑고 다른 동전들로 합을 만든다.
    while q:
        coin_sum, cnt = q.popleft()
        if k == coin_sum:
            print(cnt)
            break
				# 다른 동전들을 탐색하면서 합을 구함.
				# 합을 할 때마다 cnt를 +1 해준다.
        for coin in coins:
            temp_sum = coin_sum + coin
            temp_cnt = cnt + 1
            if temp_sum > k:
                continue
						# 만들어진적 없거나 합이 k보다 작다면 체크해주고
						# 큐에 이 금액이 만들어진 동전수와 금액을 넣어준다.
            elif temp_sum <= k and not check[temp_sum]:
                check[temp_sum] = True
                q.append((temp_sum, temp_cnt))
    if coin_sum != k:
        print(-1)

bfs()