[항해99] BFS 너비 우선 탐색

BFS?

BFS란 Breath First Search의 준말로, 한국말로는 너비 우선 탐색이라고 합니다.

너우탐 이라고 하면 아는 척을 할 수 있습니다.

 

DFS에서는 그래프의 한쪽 끝까지 간 다음에 옆쪽을 탐색했는데, BFS에서는 계속해서 옆 노드를 다 보고, 옆 노드들이 끝나면 아래 노드를 보는 식으로 탐색을 진행합니다. 

 

구현

from collections import deque

graph = {
    1: [2, 3, 4],
    2: [5],
    3: [5],
    4: [],
    5: [6, 7],
    6: [],
    7: [3],
}


def bfs_queue(start):
    visited = [start]
    q = deque([start])

    while q:
        node = q.popleft()
        for adj in graph[node]:
            if adj not in visited:
                q.append(adj)
                visited.append(adj)

    return visited

 

BFS는 한 노드에서 탐색 가능한 모든 노드를 탐색한 다음, 탐색한 노드에 대해서 BFS를 진행하므로, 큐 자료구조를 이용합니다.

 

탐색하면서 방문하지 않은 노드라면 큐에 넣고, 탐색이 끝나면 큐에 있는 노드를 꺼내서 다음 탐색을 합니다. 

BFS와 DFS 

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

1260번: DFS와 BFS

BFS 와 DFS 탐색을 구현해보고, 차이를 비교하는 기본적이면서도 중요한 문제였습니다.

 

간단하지만 꼭 풀어보시면 좋을 듯합니다! 

 

해답코드 

from collections import deque

n, m, v = map(int, input().split())

graph = [[] for i in range(n+1)]
for i in range(m):
    a, b = map(int, input().split())
    graph[b].append(a)
    graph[a].append(b)
    # 여기서 sort 안해서 입력이 이상하게 들어가고 있었음.
    # 인접 리스트가 번호순이 아니라 입력 순으로 처리되어서 오답이 생성됨
    
    graph[b].sort()
    graph[a].sort()


def dfs(node, visited):
    visited.append(node)

    for adj in graph[node]:
        if adj not in visited:
            dfs(adj, visited)

    return visited


def bfs(node):
    queue = deque()
    visited = []

    queue.append(node)
    while queue:
        curr = queue.popleft()
        if curr not in visited:

            visited.append(curr)
            for i in graph[curr]:
                queue.append(i)

    return visited


ans = dfs(v,[])
for i in ans:
    print(i, end= " ")
print()
ans = bfs(v)
for i in ans:
    print(i, end= " ")

 

Course Schedule

https://leetcode.com/problems/course-schedule/

Course Schedule - LeetCode

선행 과목이 있으면 다음 과목을 수강 못할 때, 모든 과목을 수강 가능한 지, 아닌지를 판별하는 문제입니다.

 

indegree라는 리스트를 만들어 선행이수과목이 있는 과목이 있을 때 마다 1씩 추가해주고, 선행 이수 과목을 들었으면 1을 감소시켜 0이 되면( 이수 가능 ) 큐에 넣고 순회하는 방식으로 만들었습니다.

 

이수한 과목은 따로 리스트에 저장하여 모든 과목 수와 이수 과목 수가 같으면 True를, 다르면 False를 리턴하도록 만들었습니다. 

 

해답코드

from collections import deque
from typing import List


class Solution:
    def canFinish(self, n: int, prerequisites: List[List[int]]) -> bool:
        # 인접 리스트로 구성
        adj = [[] for _ in range(n)]
        # 선행과목 이수 : 0, 미이수 : 1 이상
        indegree = [0] * n
        # 순회 끝나면 ans 에 저장
        ans = []

        for pair in prerequisites:
            course = pair[0]
            prerequisite = pair[1]
            adj[prerequisite].append(course)
            indegree[course] += 1

        queue = deque()
        for i in range(n):
            # 선이수 없는 과목 먼저 다 이수하고 ( 큐에 추가 )
            if indegree[i] == 0:
                queue.append(i)
                indegree -= 1

        # 큐를 돌면서 BFS
        while queue:
            current = queue.popleft()
            ans.append(current)

            for next_course in adj[current]:
                indegree[next_course] -= 1
                # 이수 가능해졌으니, 큐에 추가
                if indegree[next_course] == 0:
                    queue.append(next_course)

        return len(ans) == n