[Baekjoon 11724 / python / 실버2] 연결 요소의 개수

import sys

sys.setrecursionlimit(10 ** 9)  # 재귀함수 최대깊이 늘려놓기

N, M = map(int, sys.stdin.readline().split())  # 노드개수, 간선개수

graph = [[] for _ in range(N + 1)]  # 노드번호와 인덱스를 맞추기 위해 + 1

for _ in range(M):  # 연결정보 입력받기

    root, edge = map(int, sys.stdin.readline().split())

    graph[root].append(edge)

    graph[edge].append(root)

visited = [False] * (N + 1)  # 노드번호와 인덱스를 맞추기 위해 + 1

visited[0] = True  # 마지막에 False 존재 여부를 검사하기 위해 미리 안쓰는 0번 인덱스도 True로 초기화 해놓음

conn = 0  # 연결 요소 갯수 세는 변수

def dfs(graph, v, visited):  # dfs탐색 시작

    visited[v] = True

    for i in graph[v]:

        if visited[i] == False:

            dfs(graph, i, visited)

while False in visited:  # 만약 탐색했는데 안간곳이 있었다 -> 연결 요소가 추가로 있다 -> 안간 노드를 시작으로 dfs 한번 더

    start = visited.index(False)

    dfs(graph, start, visited)

    conn += 1  # 한번 탐색할 때마다 연결요소 + 1

print(conn)  # 계산된 연결요소 개수 출력

 

DFS/BFS를 활용하여 풀 수 있는 문제이다. 난 DFS를 사용해서 풀었다.

전체적인 코드는 DFS와 동일하지만 약간 다르다.

 

기존엔 visited 리스트를 만들 때 첫번째(0번 인덱스) 인자를 그냥 False로 놔뒀었지만, 이번 문제는 while문을 돌릴 때 False값 유무로 반복을 실행하기 때문에 0번 인덱스를 True로 초기화 해 두었다.

 

1번 노드를 시작으로 DFS를 돌렸는데 visited에 False가 존재한다면, 그것은 연결 요소가 추가로 있다는 뜻이다.

while문으로 visited에 False가 없을 때까지 시작 노드를 바꿔가며 DFS를 실행하는 반복문을 돌리고, DFS가 한 번 실행될 때마다 conn + 1을 한다. conn은 연결 요소의 개수다.

 

마지막으로 visited의 모든 요소가 True라면 반복을 종료하고 conn을 출력한다.