백준: 11724 연결 요소의 개수

문제

11724번: 연결 요소의 개수

 

문제 풀이

 이 문제는 방향이 없는 그래프가 주어졌을 때, 연결 요소의 개수를 찾는 문제이다. 연결 요소는 특정 노드를 시작으로 방문 가능한 다른 노드의 집합이다. 연결 요소는 다음과 같이 찾을 수 있다.

 

• 1번 노드를 시작으로 탐색을 시작한다.
  • 1번 노드 탐색 시 방문한 노드, 즉 연결 요소들을 체크한다.
  • 탐색이 완료 되면, 하나의 연결 요소를 찾은 것이다.
• 탐색 되지 않는 노드가 남아있다면, 탐색 되지 않는 노드를 시작으로 다시 탐색한다.
  • 탐색이 완료되면, 하나의 연결 요소가 추가 된다.
• 위의 과정의 반복을 통해, 연결 요소를 찾을 수 있다.
• 입력 예제 1의 경우 탐색이 완료되면 그림과 같이 2개의 연결요소가 있다는 것을 찾을 수 있다.

 즉, 정리하자면 하나의 노드를 시작으로 그래프 탐색을 시작해보고, 방문 여부를 체크하여 중복 탐색이 되지 않도록하는 것이다. 이는 1 - 3 - 2 - 4라는 연결 요소가 있다면 3, 2, 4 어떤 노드에서 시작하더라도 같은 연결 요소를 의미하기 때문이다. 한번의 그래프 탐색 후 모든 노드를 방문하였다면, 연결 요소는 1이 되고 아닐 경우는 추가적인 탐색 횟수에 따라 연결 요소가 추가되게 된다.

 

코드

from collections import deque
from sys import stdin


def bfs(start):
    global visited
    q = deque([start])

    while q:
        cur_node = q.popleft()
        for next_node in range(n):
            if graph[cur_node][next_node] and not visited[next_node]:
                visited[next_node] = True
                q.append(next_node)
    return 1

if __name__ == "__main__":
    answer = 0
    # input()을 사용할 경우, 시간 초과가 발생함
    n, m = map(int, stdin.readline().split())
    graph = [[False] * n for _ in range(n)]
    visited = [False] * n
    for _ in range(m):
        i, j = map(int, stdin.readline().split())
        # 그래프는 양방향이므로 반전하여 체크해줘야 함
        graph[i - 1][j - 1] = True
        graph[j - 1][i - 1] = True

    for node in range(n):
        if not visited[node]:
            visited[node] = True
            answer += bfs(node)

    print(answer)

 해당 문제를 풀 경우, `input()`을 사용하면 시간초과가 발생하게 된다. 따라서 `sys.stdin.readline`을 사용하여야 한다. 또한, 노드의 방문 여부를 체크 할 때, 리스트에 `append`하는 방식보다 미리 초기화된 리스트의 값을 갱신해주는 것이 효율적이다.