[BOJ] 연결 요소의 개수(11724) - PYTHON

그래프의 정점의 개수(N), 간선의 개수(M), 연결된 간선의 정보가 입력으로 주어진다. 이때 주어진 그래프에서 Connected Component(연결된 요소의 개수)를 구하는 문제다. 

출처: 위키피디아

다음과 같은 그래프가 주어진다면 Connected Component의 개수는 3개이다.

시간 복잡도: O(MN)

11724번: 연결 요소의 개수

---

풀이 과정

BFS나 DFS와 같은 그래프 탐색 방법을 활용하면 연결된 모든 노드(정점)를 방문할 수 있다. 따라서 시작점을 1~N으로 하는 총 N번의 탐색과정을 통해 연결된 요소의 개수를 구할 수 있다. 이때 시작점의 방문 여부를 비교하며 아직 방문하지 않았을 때만 정답 값에 1을 더한다.

ex)
N = 3, M = 1
간선 정보 : 1 - 2
이렇게 입력이 들어오면 1번 정점을 시작점으로 하고  BFS/DFS로 연결된 정점을 방문했을 때 1,2번 정점을 방문하게 된다. 따라서 시작점을 2로 하고 반복할 때는 이미 방문한 정점이므로 정답 값에 1을 더하지 않고 (연결된 요소의 개수로 치지 않고) 다음 정점으로 넘어간다. 

---

코드

import sys
from collections import deque
input = sys.stdin.readline
 
N, M = map(int, (input().split()))
varr = [[] for _ in range(N)]
for _ in range(M):
    a, b = map(int, input().split())
    varr[a - 1].append(b - 1)
    varr[b - 1].append(a - 1)
visit = [False] * N
answer = 0
for i in range(N):
    if visit[i]:
        continue
    answer += 1
    q = deque()
    q.append(i)
    visit[i] = True
    while len(q) > 0:
        cur = q.popleft()
        for temp in varr[cur]:
            if not visit[temp]:
                q.append(temp)
                visit[temp] = True
print(answer)

주석 추가

import sys
from collections import deque
 
input = sys.stdin.readline  # 입력 효율화
 
N, M = map(int, (input().split()))  # 정점의 개수, 간선의 개수
varr = [[] for _ in range(N)]  # 정점마다 연결 간선의 정보를 담을 2차원 배열(index:정점 value:연결된 정점배열)
for _ in range(M):
    a, b = map(int, input().split())  # 연결된 두 정점 입력 
    varr[a - 1].append(b - 1)  # 정점 정보 입력 (a점에 b점 연결), 배열은 index가 0부터 시작하므로 (값 - 1)로 접근 + 저장
    varr[b - 1].append(a - 1)  # 정점 정보 입력 (b점에 a점 연결)
visit = [False] * N  # 방문여부 확인할 배열
answer = 0  # 연결된 요소의 개수
for i in range(N):
    if visit[i]:  # 이미 방문했다면
        continue  # 다음 정점으로
    answer += 1  # 연결된 요소의 개수 + 1
    ###BFS###
    q = deque()  # BFS를 위한 Queue
    q.append(i)  # Queue의 첫 요소로 현재 정점
    visit[i] = True  # 현재 정점 방문으로 체크
    while len(q) > 0:  # Queue가 비어있지 않다면
        cur = q.popleft()  # Queue에서 정점을 꺼내서
        for temp in varr[cur]:  # 연결된 정점을 확인
            if not visit[temp]:  # 아직 방문하지 않았다면
                q.append(temp)  # Queue에 추가
                visit[temp] = True  # 방문으로 체크
print(answer)  # 전체 연결된 요소 개수 출력

---

채점 결과