[백준 11724번] 연결 요소의 개수 - python

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

📌 문제 탐색하기

목표

• 방향 없는 그래프가 주어졌을 때 연결 요소의 개수를 구해보자.

입력값

• 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2)
• 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v)
• ex)
• 6 5 1 2 2 5 5 1 3 4 4 6

출력값

• 연결 요소의 개수를 출력한다.
• ex)
• 2

📌 코드 설계하기

해결 아이디어

• 이 문제도 어제와 비슷한 그래프 문제다. 근데 달라진 점은!
• 그동안 계속 인덱스를 활용해서 그래프를 이었는데 이제는 이어질 정점의 값도 들어온다.
• 하지만 여전히 dfs로 충분히 풀 수 있는 문제이다. 어쨋든 모든 정점에 방문해서 이어져 있나 확인을 해야하고 그러기 위해서는 dfs를 사용할 수 있다.
• 그래프 탐색 방법에는 도달 가능한 모든 정점을 방문하는 알고리즘인 DFS, BFS 두 가지가 대표적인데 이 문제에서는 둘 다 사용할 수 있지만 일단 DFS로 구현해보았다.

📌 정답 코드

import sys

def dfs(n, k, cnt):
    used[n] = True
    nextnode = arr[n]
    cnt += 1
    if nextnode == k:
        return cnt
    if not used[nextnode]:
        return dfs(nextnode, k, cnt)

n, k = map(int, sys.stdin.readline().split())

arr = []
cnt = 0
for i in range (n):
    arr.append(int(sys.stdin.readline()))
    
used= [False] * (n+1)    
print(dfs(0, k, cnt) or -1)

시간 복잡도 구해보기

• 입력
  • 총 n번 입력을 진행한다. → O(N)
• for문
  • 이미 사용된 노드는 다시 처리되지 않는다.

최종 시간 복잡도: O(N)

📌 다른 풀이

import sys
from collections import deque

def bfs(start):
    queue = deque([start])
    visited[start] = True
    while queue:
        u = queue.popleft()
        for v in arr[u]:
            if not visited[v]:
                visited[v] = True
                queue.append(v)
                
n, m = map(int, sys.stdin.readline().split())
arr = [[] for i in range(n+1)]

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

visited = [False] * (n+1)

cnt = 0
for i in range(1, n+1):
    if not visited[i]:
        bfs(i)
        cnt += 1

print(cnt)

BFS로도 풀어보았다. deque를 사용해서 append로 넣고 popleft로 꺼냈다. 시작 노드에서 큐에 넣고 큐가 빌 때까지 계속 탐색을 진행하면 충분히 연결 요소의 개수를 셀 수 있다.

그냥 본인이 편한 코드를 선택하면 될 것 같다!