[DFS] 백준 11724. 연결요소 개수 (*)

문제

양방향 그래프의 연결 요소를 구하는 문제로, DFS의 대표적인 유형의 문제 중 하나이다.

 

풀이

DFS는 소스코드 프레임에 아래와 같은 것들이 자주 쓰인다.

visted = [False]*(n), count = 0, graph = [[] for _ in range(n)]

 

첫 번째 visited는 노드를 방문했는지 확인하기 위함이고, 두 번째는 문제에서 요구하는 것을 count, 마지막은 graph이다.

 

그래프의 특성에, 방향이 없다고 했기 때문에, 그래프 생성할 때 인덱스와 값을 switch해서 두번 씩 적어줘야 한다.

for i in range(m):
    u, v = map(int, input().split())
    graph[u].append(v)
    graph[v].append(u)

DFS를 최초로 호출하는 for 반복문의 길이는 n+1 이다.

전체 코드

import sys
sys.stdin =open('in.txt','rt')
input = sys.stdin.readline
sys.setrecursionlimit(10**6)  # 재귀함수 깊이 제한 풀기

n,m = map(int, input().split())
graph = [[] for _ in range(n+1)]
graph[0] = [0,0]

for i in range(m):
    u, v = map(int, input().split())
    graph[u].append(v)
    graph[v].append(u)

cnt = 0
v = [False for _ in range(n+1)]
def DFS(g, s, v):
    v[s] = True

    for i in g[s]:     # 그래프 돌면서 값 하나씩 뽑아서,
        if not v[i]:   # 방문 이력도 없으면,
            DFS(g, i, v)


for c in range(1, len(v)):
    if v[c] == False:
        cnt += 1
        DFS(graph, c, v)

print(cnt)