탐색

탐색은 대표적으로 깊이 우선 탐색(DFS)와 너비 우선 탐색(BFS)이 있다.

05-1 깊이 우선 탐색

깊이 우선 탐색(DFS: depth-first search)은 그래프 완전 탐색 기법 중 하나이다. 깊이 우선 탐색은 그래프의 시작 노드에서 출발하여 탐색할 한 쪽 분기를 정하여 최대 깊이까지 탐색을 마친 후 다른 쪽 분기로 이동하여 다시 탐색을 수행하는 알고리즘이다.

다음은 깊이 우선 탐색의 기능, 특징, 시간 복잡도를 표로 정리한 것이다. 표의 시간 복잡도는 노드 개수를 V, 에지 개수를 E로 표기했다.

기능	특징	시간복잡도(노드 수: V, 에지 수: E)
그래프 완전 탐색	- 재귀 함수로 구현	O(V + E)
	- 스택 자료구조 이용

깊이 우선 탐색은 실제 구현 시 재귀 함수를 이용하므로 스택 오버플로(stack overflow)에 유의해야 한다. 깊이 우선 탐색을 응용하여 풀 수 있는 문제는 단절점 찾기, 단절선 찾기, 사이클 찾기, 위상 정렬 등이 있다.

깊이 우선 탐색의 핵심 이론

DFS는 한 번 방문한 노드를 다시 방문하면 안 되므로 노드 방문 여부를 체크할 리스트가 필요하며, 그래프는 인접 리스트로 표현한다. 그리고 DFS의 탐색 방식은 후입 선출 특성을 가진다. DFS는 다음의 과정을 따른다.

1. DFS를 시작할 노드를 정한 후 사용할 자료구조 초기화하기

2. 스택에서 노드를 꺼낸 후 꺼낸 노드의 인접 노드를 다시 스택에 삽입하기

3. 스택 자료 구조에 값이 없을 때까지 반복하기

---

문제 023 연결 요소의 개수 구하기

문제
방향 없는 그래프가 주어졌을 때, 연결 요소 (Connected Component)의 개수를 구하는 프로그램을 작성하시오.

입력
첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주어진다.

출력
첫째 줄에 연결 요소의 개수를 출력한다.

예제 입력 1
6 5
1 2
2 5
5 1
3 4
4 6
예제 출력 1
2

---

문제를 풀기 전 먼저 연결 요소가 무엇인지 알아야 한다. connected component 라고 하는데 위키에서 내용을 찾아보면

a component of an undirected graph is a connected subgraph that is not part of any larger connected subgraph

라고 나와 있다. 어려운 말처럼 보이지만 쉽게 말하면 다른 그래프와 이어지지 않은 독립된 subgraph를 말하는 것이다.

예를 들어 위 사진에선 3개의 connected component를 가지고 있다.

다시 문제를 보면 입력에선 노드, 엣지의 개수와 에지에 대한 정보를 주고 있다. 그렇다면 문제를 풀기 위해 짜야 하는 코드는 1.그래프에 대한 정보를 입력 받는 코드, 2.방문하지 않는 노드를 탐색하는 DFS 함수, component의 갯수를 세는 코드 이렇게 3가지 로직만 짜면 문제를 풀 수 있다.

import sys
sys.setrecursionlimit(10**6)
sys.stdin = open("input.txt", 'rt')

def DFS(v):
    visited[v] = 1
    for i in A[v]:
        if not visited[i]:
            DFS(i)

if __name__ == "__main__":
    n, m = map(int, input().split())
    A = [[] for _ in range(n+1)]
    visited = [0] * (n+1)

    for _ in range(m):
        s, e = map(int, input().split())
        A[s].append(e)      #양방향 에지이므로 양쪽에 에지를 더하기
        A[e].append(s)

    cnt = 0

    for i in range(1, n+1):
        if not visited[i]:
            cnt += 1
            DFS(i)

    print(cnt)

_2023_0924 내용 보충 필요

05-2 너비 우선 탐색

너비 우선 탐색(BFS, breadth-first search)도 그래프를 완전 탐색하는 방법 중 하나로, 시작 노드에서 출발해 시작 노드를 기준으로 가까운 노드를 먼저 방문하면서 탐색하는 알고리즘이다.

기능	특징	시간복잡도(노드 수: V, 에지 수: E)
그래프 완전 탐색	- FIFO 탐색	O(V + E)
	- Queue 자료구조 이용

너비 우선 탐색은 선입선툴 방식으로 탐색하므로 큐를 이용해 구현한다. 또한 너비 우선 탐색은 탐색 시작 노드와 가까운 노드를 우선하여 탐색하므로 목표 노드에 도착하는 경로가 여러 개일 때 최단 경로를 보장한다.

너비 우선 탐색의 핵심 이론

1. BFS를 시작할 노드를 정한 후 사용할 자료구조 초기화하기

BFS도 DFS와 마찬가지로 방문했떤 노드는 다시 방문하지 않으므로 방문한 노드를 체크하기 위한 리스트가 필요하다. 그래프를 인접 리스트로 표현하는 것 역시 DFS와 동일하다. 하나 차이점이 있다면 탐색을 위해 스택이 아닌 큐를 사용한다.

2. 큐에서 노드를 꺼낸 후 꺼낸 노드의 인접 노드를 다시 큐에 삽입한다.

큐에서 노드를 꺼내면서 인접 노드를 큐에 삽입한다. 이때 방문 리스트를 체크하여 이미 방문한 노드는 큐에 삽입하지 않는다. 또한 큐에서 꺼낸 노드는 탐색 순서에 기록한다.

3. 큐 자료구조에 값이 없을 때까지 반복하기

---

문제 026 DFS와 BFS 프로그램

문제
그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다.

입력
첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사이에 여러 개의 간선이 있을 수 있다. 입력으로 주어지는 간선은 양방향이다.

출력
첫째 줄에 DFS를 수행한 결과를, 그 다음 줄에는 BFS를 수행한 결과를 출력한다. V부터 방문된 점을 순서대로 출력하면 된다.

예제 입력 1
4 5 1
1 2
1 3
1 4
2 4
3 4
예제 출력 1
1 2 4 3
1 2 3 4

---

기본적인 DFS와 BFS가 합쳐진 문제이다. DFS는 023번 문제에서 설명했으므로 여기선 BFS만 설명한다. BFS는 재귀함수로는 풀 수 없으므로 from collections import deque처럼 덱을 import 해주고 큐를 이용해 풀어야 한다. BFS를 구현하는 과정은 다음과 같다. 1.시작 노드를 큐에 추가하고 체크한다. 2.리스트를 돌며 방문하지 않는 노드가 있다면 체크하고 인접 노드를 큐에 추가한다. 3.큐가 비어있을 때까지 반복한다. 이렇게 하면 번호가 작은 노드부터 돌 수 있다.

import sys
sys.setrecursionlimit(10**6)
sys.stdin = open("input.txt", 'rt')
from collections import deque

def DFS(v):
    visited[v] = 1
    print(v, end=" ")
    for i in A[v]:
        if not visited[i]:
            DFS(i)

def BFS(v):
    queue = deque()
    queue.append(v)
    visited[v] = 1
    while queue:
        now = queue.popleft()
        print(now, end=" ")
        for i in A[now]:
            if not visited[i]:
                visited[i] = 1
                queue.append(i)

if __name__ == "__main__":
    n, m, start = map(int, input().split())
    A = [[] for _ in range(n+1)]
    visited = [0] * (n+1)

    for _ in range(m):
        s, e = map(int, input().split())
        A[s].append(e)
        A[e].append(s)

    for i in range(n+1):
        A[i].sort()

    DFS(start)
    print()
    visited = [0] * (n+1)
    BFS(start)

_내용, 문제 추가 필요