[Python] 1178번 간선 추가

 

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

---

 

24/09/02

 

 

몇 번 잘못된 접근을 한 문제였기 때문에 어떻게 잘못된 접근을 했는지를 중심으로 적어보겠다.

---

 

문제 접근 방식:

 

 

먼저 한붓그리기라는 점에서 오일러 경로 문제임을 파악했다.

 

오일러 경로가 존재하려면 그래프 정점의 차수를 모두 센 다음에, 차수가 홀수인 정점이 0개 혹은 2개 있어야 한다.

이러한 사실을 기반으로, 처음에는 다음과 같은 접근 방식을 세웠다.

 

먼저, 한붓그리기를 하려면 모든 정점이 서로 이어져 있어야 한다.

 

따라서, 정점의 차수가 0이라면 그 누구와도 이어져 있지 않으므로, 이것을 고려해주었다. 그리고 오일러 경로가 존재하려면 차수가 홀수인 정점이 0개 혹은 2개 있어야 한다는 사실에 기반하여, 정점의 차수가 홀수인 경우를 고려해주었다.

 

그리고 차수가 짝수인 정점, 즉, 2나 4와 같은 경우, 이미 누군가와 이어져있고 정점의 차수가 짝수이므로, 굳이 이 정점에 간선을 더 그릴 필요가 없다고 생각하여 이러한 정점은 건들지 않는 것이 최선이라고 생각했다.

 

 

예를 들어, 정점이 5개이고 모든 정점의 차수가 [0, 0, 0, 0, 0]이라고 하자.

 

1. 먼저 0인것끼리 이어줬다. 그러면 정점의 차수들은 [1, 1, 1, 1, 0]이 될 것이다.

 

2. 이렇게 차수가 0인 정점이 하나 남는 경우, 홀수 차수인 정점에 아무거나 잇는다. 그러면 [2, 1, 1, 1, 1]이 될 것이다.

 

3. 이후 차수가 홀수인 정점이 2개보다 크다면 2개가 남을 때까지 홀수 차수 정점끼리 잇는다. 그러면 [2, 2, 2, 1, 1]이 될 것이다.

 

4. 만약 이 과정에서 홀수 차수 정점이 한개만 남는다면 불가능하다고 판단했다.

 

이렇게 생각하고 구현했는데, 틀렸다.

 

 

반례는 다음과 같았다.

 

정점이 6개이고, 간선이 다음과 같이 주어져 있다고 해보자.

 

$$(1, 2), (2, 3), (3, 1), (4, 5), (5, 6), (6, 4)$$

 

즉, 1번부터 3번 정점까지 서로 삼각형 모양으로 이어져있고, 4번 정점부터 6번 정점까지 서로 삼각형 모양으로 이어져있다.

 

이 경우 모든 정점의 차수는 짝수이기 때문에, 위의 방식에 의하면 간선을 더 이상 잇지 않아도 한붓그리기가 가능하다고 판단한다.

 

실제로는 두 요소가 서로 "연결"되어야 하기 때문에 두 요소를 이어주는 2개의 간선을 더 추가해줘야한다.

 

즉, 이 알고리즘에는 요소의 연결성을 고려하지 않았다.

 

 

요소의 연결 여부를 따지려면 어떻게 해줘야 할까? 가장 먼저 생각나는 것은 유니온파인드(분리집합)이다.

 

간선을 추가할 때 두 정점을 유니온 해주면 된다.

 

위의 접근 방식과 동일하게 차수가 0이거나 홀수인 정점 먼저 연결해주되, 모든 정점이 하나로 이어질 때 까지 반복해서 간선을 추가해주면 된다.

---

아래는 내가 위의 접근 방식과 같이 작성한 파이썬 코드이다. 더보기를 누르면 확인할 수 있다.

# 1178번 간선 추가
# 오일러 경로, 유파
'''
접근 방법:
먼저 연결이 되어있어야 함.
처리해줘야 할 것은 두가지.
1. degree 0인 경우
2. degree 홀수인 경우
짝수인 경우는 놔두면 됨.
1. 먼저 degree가 0인것끼리 모두 잇는다.
ex) 0 0 0 0 0
-> 1 1 1 1 0
2. 0이 하나 남는 경우 홀수 차수에 아무거나 잇는다.
-> 1 1 1 2 1
3. 홀수 차수끼리 잇는다. (2개가 될 때까지)
-> 2 2 1 2 1
4. 홀수 차수가 1개 남는 경우는 존재하지 않는다.
따라서 여기서 멈추면 끝.
+ 반례를 발견함
test case 1)
6 6
1 2
2 3
3 1
4 5
5 6
6 4
answer : 1
test case 2)
6 3
1 2
2 3
3 1
answer : 3
disjoint면 차수가 0이거나 홀수인 노드 먼저 union을 시켜준다.
'''
import sys
input = sys.stdin.readline

# 정점과 간선의 개수
V, E = map(int, input().split())
degree = [0 for _ in range(V)]
# 유파
parent = [i for i in range(V)]
def find(node):
    if parent[node] != node:
        parent[node] = find(parent[node])
    return parent[node]
def union(node1, node2):
    parent1 = find(node1)
    parent2 = find(node2)
    if parent1 < parent2:
        parent[parent2] = parent1
    else:
        parent[parent1] = parent2

for i in range(E):
    a, b = map(lambda x: int(x)-1, input().split())
    degree[a] += 1
    degree[b] += 1
    union(a, b)
ans = 0
P = find(0)
for i in range(V):
    if find(i) != P:
        Pi = find(i)
        S0, S1 = [], []
        for j in range(V):
            if P == find(j):
                S0.append(j)
            if Pi == find(j):
                S1.append(j)
        a, b = 0, i
        for node in S0:
            if degree[node] == 0 or degree[node] % 2 == 1:
                a = node
                break
        for node in S1:
            if degree[node] == 0 or degree[node] % 2 == 1:
                b = node
                break
        degree[a] += 1
        degree[b] += 1
        ans += 1
        union(0, i)
odd_node_num = 0
for i in range(V):
    if degree[i] % 2:
        odd_node_num += 1
if odd_node_num > 2:
    odd_node_num -= 2
    ans += odd_node_num//2
print(ans)