[Baekjoon] 11724번 : 연결 요소의 개수 (Python, BFS, DFS, 최소 신장 트리 응용)

[Baekjoon] 11724번 : 연결 요소의 개수 (Python, BFS, DFS, 최소 신장 트리 응용)

 

목차

 

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

11724번: 연결 요소의 개수

코드 링크

https://github.com/stellaluminary/Baekjoon

GitHub - stellaluminary/Baekjoon

Python

 

방법 1 - 메모리 64376KB / 시간 804ms / 코드 길이 560B

 

본 문제는 방향이 없는 그래프라는 내용이 명시되어 있으므로 당연히 graph에 대한 구성을 예상해볼 수 있다.

이에 따라 node와 edge가 주어지고 서로 연결된 그룹의 개수를 구하는 문제를 나타낸다.

 

이때 우리는 DFS 혹은 BFS를 활용한 내용을 고려해볼 수 있다.

visist을 통해 그곳을 방문했는지를 기반으로 방문하지 않았다면 DFS 혹은 BFS로 연결된 곳들에 대한 graph node를 모두 방문 처리한 후 counting 해주면 된다.

만약 방문 처리가 되었다면 pass

 

 

from collections import deque
import sys
input = sys.stdin.readline

def bfs(s):
    q = deque([s])
    visit[s]=True
    while q:
        now = q.popleft()
        for i in graph[now]:
            if not visit[i]:
                visit[i] = True
                q.append(i)

n, m = map(int, input().split())
visit = [0]*(n+1)
graph = [[] for _ in range(n+1)]

for i in range(m):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)

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

print(cnt)

 

방법 2 - 메모리 90204KB / 시간 1192ms / 코드 길이 477B

 

최소 신장 트리, 크루스칼 알고리즘을 공부하다보니 본 그래프 문제를 다음과 같이도 풀 수 있다.

굳이 graph를 그리지 않더라도 애초에 edge 기반으로 입력을 받았으니 이를 기반으로 하는 결합을 진행하고 이 결합된 부모 노드가 같으면 같은 그룹으로 묶을 수 있다.

 

그런 아이디어에서 union을 통한 부모 노드로의 결합 후 한 번 더 후처리를 진행하여 unique한 값들만 뽑아 길이를 출력하면 결국 그룹의 숫자를 알 수 있게 된다.

 

 

import sys
input = sys.stdin.readline

def f_p(p, x):
    if p[x] != x:
        p[x] = f_p(p, p[x])
    return p[x]

def union(p, a, b):
    a, b = f_p(p, a), f_p(p, b)
    p[max(a,b)] = min(a, b)

n, m = map(int, input().split())

p = [i for i in range(n+1)]
edges = []
for i in range(m):
    a, b = map(int, input().split())
    edges.append((a,b))

for edge in edges:
    a, b = edge
    union(p, a, b)

for i in range(1,n+1):
    p[i] = f_p(p, p[i])

print(len(set(p[1:])))