[Python, 백준/11724번] 연결 요소의 개수

---

☑️ [Python, 백준/11724번] 연결 요소의 개수

1️⃣ 문제

https://www.acmicpc.net/problem/11724

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

 

2️⃣ 접근

그래프 문제들은 예제 입력의 경우, 숫자로 전달하기 때문에 입력 값 설명을 유심히 봐야한다. 대부분 형태가 Vertex Count와 Edge Count 그리고 다음 줄에는 Edge Data를 전달하지만 이렇게 문자를 보는 것은 머릿속에서 쉽게 떠올리기 힘들다.

 

그래서 일단 그릴 수 있다면 그려본다. 예제 입력 1에 있는 데이터를 시각화 한다면, 다음과 같은 그래프가 나온다.

 

시각적으로 그려보면 출력 값이 2라는 사실을 직관적으로 알 수 있다. 그리고 연결 되었다는 것은 단절된 부분 그래프의 수와 동일핟단 점을 캐치 할 수 있다. 그러면 이제 DFS를 통해서 모든 노드를 순회하면 된다.

 

순회는 2가지만 생각하면 된다. 첫번째로 모든 노드를 순회하기 위해서 정점 집합 데이터를 돌리는 것, 두번째로는 한 노드를 가지고 해당 노드와 인접한 노드가 있는지 확인하는 순회다. 이전 블로그 게시글에서는 이를 DFS 함수와 DFS_VISIT 함수로 나눴다.

[알고리즘] DFS, BFS

 

DFS 함수에서는 방문 처리가 True인 노드는 순회되었다고 생각하고 False인 노드들에 한해서만 순회한다. 첫번째 순서를 제외하고 다음으로 해당 IF문에 진입할 수 있는 노드가 있다면 이전 처리에서 모든 Node를 방문하지 못했다는 소리가 되며, 첫번째 탐색한 노드로 모든 노드를 순회할 수 없음을 알 수 있다.

 

그렇기 때문에 DFS 함수의 IF문 안에서 Sum 변수를 선언해서 값을 증가시켜서 해결했다.

 

3️⃣ 코드

import sys
sys.setrecursionlimit(10**6)

n_count, e_count = map(int, sys.stdin.readline().split())

graph = [[0]*(n_count+1) for _ in range(n_count+1)]
for i in range (e_count):
    a,b = map(int, sys.stdin.readline().split())
    graph[a][b] = graph[b][a] = 1
    
visit = [False] * (n_count + 1)
sum = 0

def dfs() -> int:
    global sum
    for i in range(1, len(graph)):
        for j in range(1, len(graph[i])):
            if visit[j] == False:
                dfs_visit(j)
                sum += 1
    return sum
                
def dfs_visit(node):
    visit[node] = True
    
    for i in range(len(graph[node])):
        if graph[node][i] == 1 and visit[i] == False:
            dfs_visit(i)
            
if __name__ == '__main__':
    print(dfs())