BOJ(백준) 11724[연결 요소의 개수]

안녕하세요, 이번 글에서는 백준 11724번 문제인 “연결 요소의 개수” 문제를 함께 해결해 보겠습니다. 이 문제는 주어진 그래프에서 연결 요소의 개수를 구하는 문제입니다. 문제를 분석하고, 접근 방법을 정리한 후, 최종적인 정답 코드를 확인해 보겠습니다.

 

문제 URL: https://www.acmicpc.net/problem/11724

1. 문제 설명

1) 문제 개요

주어진 그래프에서 연결 요소의 개수를 구하는 문제입니다. 연결 요소란 그래프 내에서 서로 연결된 정점들의 부분 집합으로, 다른 정점들과는 연결되지 않은 집합을 말합니다.

 

2) 입력

• 첫 번째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000)과 간선의 개수 M(0 ≤ M ≤ 10,000)이 주어집니다.

• 두 번째 줄부터 M개의 줄에 걸쳐 간선의 정보가 주어집니다. 각 줄은 두 개의 정점 a, b로 이루어지며, 이는 a번 정점과 b번 정점이 연결되어 있다는 의미입니다. (1 ≤ a, b ≤ N)

 

3) 출력

• 그래프의 연결 요소의 개수를 출력합니다.

 

2. 접근법

1) 입력받기

• sys.stdin.readline을 사용하여 입력 속도를 높입니다.

• 정점의 개수와 간선의 개수를 입력받고, 간선 정보를 입력받아 인접 리스트를 만듭니다.

 

2) 연결 요소 찾기

• 모든 정점을 방문하면서 BFS(또는 DFS)를 사용하여 연결 요소를 찾습니다.

• 방문하지 않은 정점을 시작으로 BFS를 수행하여 연결된 모든 정점을 방문합니다.

• BFS가 종료될 때마다 연결 요소의 개수를 증가시킵니다.

 

3. 정답 코드

import sys
input = sys.stdin.readline

# 노드의 개수(N)와 간선의 개수(M)를 입력 받음
N, M = map(int, input().split())

# 그래프의 인접 리스트 초기화
adj = [[] for _ in range(N)]

# 모든 간선을 읽어 인접 리스트에 추가
for _ in range(M):
    a, b = map(int, input().split())
    a -= 1  # 입력 값은 1부터 시작하므로 0부터 시작하도록 조정
    b -= 1
    adj[a].append(b)
    adj[b].append(a)

# 각 노드의 방문 여부를 체크하는 리스트
chk = [0] * N

# 연결 요소의 개수를 세는 변수
ans = 0

# 모든 노드를 방문할 때까지 반복
while chk.count(0) > 0:
    q = []
    q.append(chk.index(0))  # 방문하지 않은 노드의 인덱스를 큐에 추가
    chk[q[0]] = 1           # 해당 노드를 방문했다고 표시
    
    # BFS를 사용하여 연결된 모든 노드를 방문
    while len(q) > 0:
        s = q.pop(0)
        for i in adj[s]:
            if chk[i] == 0:     # 방문하지 않은 노드를 찾으면
                chk[i] = 1      # 방문 표시를 하고
                q.append(i)     # 큐에 추가
    
    # 연결 요소의 개수 증가
    ans += 1

# 연결 요소의 개수를 출력
print(ans)

4. 코드 설명

1) 입력 받기

• 첫 번째 줄에서 정점의 개수 N과 간선의 개수 M을 입력받습니다.

• 두 번째 줄부터 M개의 간선을 입력받아 인접 리스트를 만듭니다.

 

2) 변수 초기화

• adj 배열: 각 정점의 인접 정점 리스트를 저장합니다.

• chk 배열: 각 정점의 방문 여부를 저장합니다.

• ans 변수: 연결 요소의 개수를 저장합니다.

 

3) 연결 요소 찾기

• 방문하지 않은 정점을 찾아 BFS를 시작합니다.

• BFS를 통해 연결된 모든 정점을 방문하고, 연결 요소의 개수를 증가시킵니다.

 

4) 최종 출력

• 연결 요소의 개수를 출력합니다.

 

예시

1] 입력

6 5

1 2

2 5

5 1

3 4

4 6

 

2] 그래프의 인접 리스트 생성

• 인접 리스트 adj는 다음과 같이 초기화된다

adj = [

    [1, 4],  # 정점 1의 인접 정점: 2, 5

    [0, 4],  # 정점 2의 인접 정점: 1, 5

    [],      # 정점 3의 인접 정점: 없음

    [3, 5],  # 정점 4의 인접 정점: 4, 6

    [0, 1],  # 정점 5의 인접 정점: 1, 2

    [3]      # 정점 6의 인접 정점: 4

]

 

3] 연결 요소 찾기

• BFS를 통해 연결 요소를 찾는다.

• 예를 들어, chk 배열과 ans 변수를 업데이트하는 과정은 다음과 같다:

(1) 첫 번째 연결 요소 찾기

• 방문하지 않은 첫 번째 정점은 1이다.

• BFS를 시작하여 연결된 모든 정점을 방문:

• 정점 1 방문: chk = [1, 0, 0, 0, 0, 0]

• 정점 2 방문: chk = [1, 1, 0, 0, 0, 0]

• 정점 5 방문: chk = [1, 1, 0, 0, 1, 0]

• BFS 종료 후, 연결 요소 개수 증가: ans = 1

(2) 두 번째 연결 요소 찾기

• 방문하지 않은 다음 정점은 3이다.

• BFS를 시작하여 연결된 모든 정점을 방문:

• 정점 3 방문: chk = [1, 1, 1, 0, 1, 0]

• 정점 4 방문: chk = [1, 1, 1, 1, 1, 0]

• 정점 6 방문: chk = [1, 1, 1, 1, 1, 1]

• BFS 종료 후, 연결 요소 개수 증가: ans = 2

 

4] 최종 출력

• 모든 정점을 방문했으므로 연결 요소의 개수는 2이다.

• 최종 출력: 2

 

 

 

시간 복잡도
이 문제에서 사용한 알고리즘은 BFS(또는 DFS)를 이용한 연결 요소 찾기입니다. 시간 복잡도는 다음과 같이 분석할 수 있습니다:

• 그래프의 모든 정점을 한 번씩 방문하고, 모든 간선을 한 번씩 탐색합니다.
• 각 정점에 대해 BFS를 수행할 때, 해당 정점과 연결된 모든 간선을 확인합니다.

 

따라서, 시간 복잡도는 정점의 수를  N , 간선의 수를  M 이라 할 때,  O(N + M) 입니다.

5. Github으로 확인

coTest/BOJ/BOJ01_09_01_11724.py at main · pcy4196/coTest