DFS/BFS

엄혜영·2024년 3월 29일

BFS DFS algorithm

알고리즘 챌린저까지

목록 보기

7/11

DFS/BFS는 그래프 탐색의 방법이다.

그래프 탐색의 목적은 모든 정점을 한 번찍 방문 하는데에 있다.

DFS, Depth-First Search

깊이 우선 탐색이란

루트 노드에서 시작해서 다음 분기로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법이다.

한 방향으로 갈 수 있을 때까지 가다가 더 이상 갈 수 없게 되면 가장 가까운 갈림길로 돌아와서 다른 방향으로 탐색을 진행하는 방법이다.

모든 노드를 방문하고자 하는 경우에 이 방법을 선택한다.

특징

깊이 우선 탐색이 너비 우선 탐색에 비해서 구현은 간단하나, 검색 속도는 느리다.

자기 자신을 호출하는 순환 알고리즘의 형태를 가지고 있다. (재귀적으로 동작한다)

stack과 재귀호출을 이용하여 구현한다.

그래프 탐색을 할 때 어떤 노드를 방문했었는지에 대한 검새를 반드시 해야 한다는 것이다.

시간 복잡도

정점의 수 N, 간선의 수 E
인접 리스트로 표현된 그래프: O(N+E)
인접 행렬로 표현된 그래프: O(N^2)

적은 수의 간선을 가지는 희소 그래프 - 인접 리스트 사용이 유리

# DFS 메서드 정의
def dfs(graph, v, visited):
	# 현재 노드를 방문 처리
    visited[v] = True
    print(v, end=' ')
    # 현재 노드와 연결된 다른 노드를 재귀적으로 방문
    for i in graph[v]:
        if not visited[i]:
            dfs(graph, i, visited)

BFS, Breath-First Search

너비 우선 탐색이란

루트 노드에서 시작해서 인접한 노드를 먼저 탐색하는 방법이다.

시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법이다.

두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을 때 이 방법을 선택한다.

특징

깊이 우선 탐색에 비해 구현이 복잡하다.

BFS는 재귀적으로 동작하지 않는다.

그래프 탐색을 할 때 어떤 노드를 방문했는지 여부를 검사해야 한다.

방문할 노드들을 차례로 저장한 후 꺼낼 수 있는 자료구조인 큐(Queue)를 사용한다.

시간 복잡도

인접 리스트로 표현된 그래프: O(N+E)
인접 행렬로 표현된 그래프: O(N^2)
DFS와 마찬가지로 그래프 내에 적은 숫자의 간선만을 가지는 희소 그래프의 경우 인접 리스트를 사용하는 것이 유리하다.

#BFS 메서드 정의
def bfs(graph, start, visited):
	# Queue 구현을 위해 deque 라이브러리 사용
    queue = deque([start])
    # 현재 노드를 방문 처리
    visited[start] = True
    # 큐가 빌 때까지 반복
    while queue:
    	# 큐에서 하나의 원소를 뽑아 출력
        v = queue.popleft()
        print(v, end=' ')
        # 아직 방문하지 않은 인접한 원소들을 큐에 삽입
        for i in graph[v]:
            if not visited[i]:
                queue.append(i)
                visited[i] = True

문제 풀이

인접 노드에 대한 규칙 X
11724번 - 연결 요소의 개수

import sys
from collections import deque

def bfs(n):
    queue = deque()
    queue.append(n)
    visited[n] = True

    if n not in graph:
        return

    while queue:
        n = queue.popleft()
        for i in graph.get(n):
            if visited[i]==True:
                continue
            visited[i] = True
            queue.append(i)

n, m = map(int, input().split())
if m==0:
    print(n)
    sys.exit()
visited = [False] * (n+1)
graph = {}
for i in range(m):
    n1, n2 = map(int, sys.stdin.readline().split())
    if n1 in graph:
        graph[n1].append(n2)
    else:
        graph[n1] = [n2]
    if n2 in graph:
        graph[n2].append(n1)
    else:
        graph[n2] = [n1]

cnt = 0
for i in range(1, n+1):
    if visited[i]==False:
        bfs(i)
        cnt+=1
print(cnt)

인접 노드에 대한 정보를 직접 저장해주어야 한다.

개인적으로, 인접 노드를 저장할 때 딕셔너리를 사용하는 것을 선호한다.

방향 없는 그래프로 명시되어 있는 경우 (6, 5)를 저장할 때 6→5와 5→6 둘 다 저장해야 함에 주의하자!

인접 노드에 대한 규칙 O
2667번 - 단지번호붙이기

from collections import deque

def bfs(x, y):
    if graph[x][y]==0:
        return 0

    cnt = 0
    queue = deque()
    queue.append((x, y))
    graph[x][y] = 0

    while queue:
        x, y = queue.popleft()
        cnt+=1
        for i in range(4):
            xm = x + xMove[i]
            ym = y + yMove[i]

            if xm<0 or xm>=n or ym<0 or ym>=n:
                continue
            if graph[xm][ym] == 0:
                continue
            
            graph[xm][ym] = 0
            queue.append((xm, ym))
    return cnt


xMove = [1, -1, 0, 0]
yMove = [0, 0, 1, -1]
graph = []
house = []
n = int(input())
for i in range(n):
    line = list(map(int, input()))
    graph.append(line)

for i in range(n):
    for j in range(n):
        result = bfs(i, j)
        if result != 0:
            house.append(result)
house.sort()
print(len(house))
for i in house:
    print(i)