[백준알고리즘] 11724번: 연결 요소의 개수 -Python

[백준알고리즘] 11724번: 연결 요소의 개수 -Python

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

11724번: 연결 요소의 개수

두 가지 방법을 풀었다. 이 문제는 주어진 연결 정보를 가지고 그래프가 몇 개가 생성이 되는지 찾는 문제이다. 처음에는 Disjoint Set (서로 베타적인 집합)을 나타내기 위해서 Union-Find와 유사한 알고리즘을 만들었다. 이후 질문 게시판이나 다른 분들의 코드를 보니 DFS, BFS로 많이들 풀었길래 DFS로 풀어보았다.

 

우선 문제를 풀기 전에 틀렸던 반례를 하나 소개하겠다.

4 1

1 2

-> Output: 3

 

하나의 정점도 하나의 그래프이기 때문에 하나의 연결 요소로 인정해주어야 한다. 때문에 Disjoint Set 문제라고 생각할 수 있다.

 

1. Union-Find

Union-Find를 적용하기 위해서 두 정점이 연결될 때가 중요하다. 나는 3가지의 경우로 생각했다.

1. 주어진 두 정점이 모두 두 정점 이상이 포함된 집합에 포함되어있는 경우

2. 주어진 두 정점 중에 하나의 정점만 두 정점 이상이 포함된 집합에 포함되어있는 경우

3. 주어진 두 정점이 모두 두 정점 이상이 포함된 집합에 포함되어있지 않는 경우

 

첫 번째 예제 입력을 보자면 (1 2) (2 5) (5 1) (3 4) (4 6)의 연결 정보가 있다. 순서대로 생각해보면 처음 (1 2)는 3의 경우이다. 처음에는 두 정점 모두 각자 하나의 점의 모습으로 존재하는 각각의 그래프이기 때문이다.

 

여기서 다음 (2 5)가 주어지게 되면, 2의 경우가 된다. 정점 2의 경우에는 이미 1과 연결되어 두 정점 이상 존재하는 그래프에 속해있지만 5는 그 자체로 정점이 그래프이기 때문이다.

 

다음 (5 1)이 주어지게 되면, 1의 경우가 된다. 첫 번째 입력 예제에서는 서로 다른 두 set이 합쳐지는 경우는 존재하지 않지만 여기서처럼 서로 같은 집합이 주어진 경우도 살펴봐야 한다. 서로 다른 두 set이 합쳐지는 경우는 두 번째 입력 예제에서 (5 4)가 주어질 때로 볼 수 있다.

 

이렇다고 할 때, head라는 리스트를 통해 각 vertex가 연결되어있는 vertex를 값으로 갖도록 했다. 문제에서는 방향성이 없지만, 임의로 방향성이 있다고 고려하고 왼쪽 vertex에 오른쪽 vertex가 추가되듯이 생각했다.

head와는 별개로 table이라는 딕셔너리를 통해 root를 key로 갖는 서로 연결된 집합들을 리스트로 갖고 있도록했다.

 

여기서는 주어진 두 정점이 모두 두 개 이상의 정점이 포함된 집합에 포함되는 경우가 중요하다고 생각한다. 두 정점 모두 head를 반복해서 이동함으로써 root를 찾을 수 있다. root의 경우 상위로 연결된 정보가 없기 때문에 head 리스트에 자신을 갖고 있기 때문이다. 그렇게 찾은 두 root가 같은 경우에는 주어진 두 정점이 이미 같은 집합에 존재한다고 생각할 수 있는 것이고, 다를 경우에는 다른 집합에 포함된 상태라는 것을 알 수 있다.

 

만약 서로 다른 두 집합에 포함된 두 정점이 주어진다면, 두 집합이 합쳐지게 되는 것이기 때문에 하나의 root에 다른 하나의 root를 연결시킨 것을 표현하기 위해서 head 리스트에 적용해준다. 그리고 실질적으로 두 집합의 원소를 합치기 위해 table에 root를 키로 갖는 리스트를 합쳐준다.

 

여기서 Union-Find를 야매처럼 했고 시간이나 코드를 더 줄일 수 있었을 것 같은데 천천히 생각해봐야겠다.

import sys

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

table = {}
for i in range(1, n+1):
    table[i] = [i]
head = [0] * (n+1)

def add_group(v1, v2):
    global head
    if head[v1] and head[v2]:
        h1, h2 = head[v1], head[v2]
        while h1 != head[h1]:
            h1 = head[h1]
        while h2 != head[h2]:
            h2 = head[h2]
        
        if h1 != h2:
            table[h1].extend(table.pop(h2))
            head[h2] = h1
    elif head[v1]:
        head[v2], h = v1, head[v1]
        while h != head[h]:
            h = head[h]
        table[h].append(v2)
        table.pop(v2)
    elif head[v2]:
        head[v1], h = v2, head[v2]
        while h != head[h]:
            h = head[h]
        table[h].append(v1)
        table.pop(v1)
    else:
        val = min(v1, v2)
        head[v1], head[v2] = val, val
        table.pop(v1)
        table.pop(v2)
        table[val] = [v1, v2]

for _ in range(m):
    v1, v2 = map(int, sys.stdin.readline().split())
    add_group(v1, v2)

key = table.keys()
cnt = 0
for i in range(1, n+1):
    if i in key:
        cnt += 1

sys.stdout.write(str(cnt))

 

2. DFS

DFS와 BFS로 많이들 푸는 것 같은데, 파이썬은 리스트로 스택을 이용할 수 있기 때문에 그냥 DFS로 구현했다.

 

DFS로 문제를 풀 때는 모든 연결 정보를 입력받은 후에 방문하지 않은 vertex가 있을 경우 각각을 root로 하는 그래프를 만드는 것이다. 방문하지 않는 vertex를 root로 그래프를 시작할 때 Disjoint Set을 하나씩 count 시켜주었다.

 

그래프를 직접 출력하는 것은 아니기 때문에 그저 사용했던 정점인지만 체크하면 되기 때문에 코드가 더 간단했다.

import sys

n, m = map(int, sys.stdin.readline().split())
graph = [[] for _ in range(n+1)]

for _ in range(m):
    v1, v2 = map(int, sys.stdin.readline().split())
    graph[v1].append(v2)
    graph[v2].append(v1)

visited = [0] * (n+1)
group = 0

# DFS
def find_tree(init):
    global visited
    stack = [init]
    while stack:
        v = stack.pop()
        if not visited[v]:
            visited[v] = 1
            for g in graph[v]:
                if not visited[g]:
                    stack.append(g)

for i in range(1, n+1):
    # 그룹핑
    if not visited[i]:
        group += 1
        find_tree(i)

sys.stdout.write(str(group))

 

잘못된 점이나 부족한 점 지적해주시면 감사하겠습니다