DFS - (1)

깊이 우선 탐색(dfs)
그래프의 시작 노드에서 출발하여, 한쪽 분기를 정해, 최대 깊이까지 탐색하는 알고리즘.
한번 방문한 노드는 다시 방문해서는 안된다.

구현 방법

• 재귀 함수
• 스택 이용

시간복잡도

• O(V+E) (노드 수 + 선분 수)

구현 구체화 방법
1. 그래프를 인접 리스트로 표현하기.
ex)
1번 노드와 인접한 노드가 2,3 번이라면
list[1]={2,3}
2. 방문 리스트 추가하기.
ex)
만약 1번 노드를 방문(stack에 input)했다면 visit[1]=true
3. stack에 pop 하며 인접 리스트 내용을 stack에 input (vist[2]=true, visit[3]=true), 이때 방문한 노드는 추가 안함.
4. stack이 빌 때까지 반복.

연결 요소의 개수 구하기

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

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

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

입력 예시
6 5
1 2
2 5
5 1
3 4
4 6

출력 예시
2

코드 예시

import sys
input = sys.stdin.readline
n, m = map(int, input().split())
stack = []
visit = [False] * (n + 1)
lst = [[] for _ in range(n + 1)]
count = 0
for _ in range(m):
    a, b = map(int, input().split())
    lst[a].append(b)
    lst[b].append(a)
while False in visit[1:]:
    count += 1
    stack.append(next(i for i in range(1, n + 1) if not visit[i]))
    while stack:
        a = stack.pop()
        if visit[a]:
            continue
        visit[a] = True
        stack.extend(i for i in lst[a] if not visit[i])
print(count)

가장 첫번째로, visit[i]=False 인 i를 stack에 넣고 순차적으로 시작한다.
stack에 숫자가 존재하면, pop을 해서 visit[a] 이면 lst[a] 의 인접한 노드들을 stack에 넣는다.(visit 이 false 인 얘들만)