11724번: 연결 요소의 개수(9 / 12) - 실버 2

3 초

512 MB

142037

64027

42047

42.052%

문제

방향 없는 그래프가 주어졌을 때, 연결 요소 (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

예제 입력 2

6 8
1 2
2 5
5 1
3 4
4 6
5 4
2 4
2 3

예제 출력 2

1

코드 

import sys

# 노드의 개수 n, 간선의 개수 m 입력
n, m = map(int, sys.stdin.readline().split())

# 노드의 개수만큼 2차원 배열 초기화
graph = [[] for _ in range(n + 1)]  # 노드는 1부터이므로 n + 1을 한다.

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

# 각 노드를 정렬할 필요는 없음

# 방문 여부 체크
visited = [False] * (n + 1)
count = 0

# dfs - 재귀함수 -> Recursion Error 발생
# sys.setrecursionlimit(10**6) 으로 정답 처리
# def dfs_function(v):
#     # 방문 처리
#     visited[v] = True
#     for i in graph[v]:  # 2, 5
#         if not visited[i]:
#             dfs_function(i)

# stack을 활용하여 문제 해결
def dfs_stack(v):
    # stack에 노드 추가
    stack = [v]
    visited[v] = True

    # stack이 비게 될 때 까지 반복
    while stack:
        node = stack.pop()
        for i in graph[node]:  # 2, 5
            if not visited[i]:
                stack.append(i)
                **visited[i] = True**  # append를 하고 방문처리를 해야함

for j in range(1, n + 1):  # 1
    if not visited[j]:
        dfs_stack(j)
        count += 1

print(count)

1. graph = [[] for _ in range(n + 1)]
   • 노드 + 1개 만큼 2차원 리스트를 초기화한다.
2. visited = [False] * (n + 1)
   • 방문 처리를 위한 visited도 노드 + 1개 만큼으로 초기화한다.
3. dfs_stack() 를 초기화한다.
   • stack = [v]
   • visited[v] = True
   • while stack
     • stack이 비게 될 때까지 루프를 돈다.
     • 연결된 노드를 알기 위해, pop을 한다.
     • for문을 돌며, 연결된 요소들을 stack에 넣어주고 방문처리를 한다.
4. 연결 요소의 개수를 파악하는 문제이므로, 노드의 처음부터 끝까지 for 루프를 돌며 확인해야한다.
   • 방문하지 않은 경우, dfs 함수에 넣어주고, 해당 함수가 끝나면 count + 1 을 해준다.
     • dfs함수가 끝났다는 것은, 방문 노드와 연결된 모든 노드를 방문 처리했다는 것을 의미한다.

핵심 포인트

1. while stack: 에서 stack에 방문하지 않은 노드를 append 한 후, 반드시 visited[i] = True 를 해야 한다.
   • 방문처리가 되지 않는다면, not visited 조건문에 걸리지 않아, 무한 루프에 빠지게 된다.
2. 이 문제도 마찬가지로, 재귀함수로 접근하였으나, Recursion Error가 발생하였다. 웬만하면 dfs문제는 stack을 활용하여 풀도록 해야겠다.