문제 소개
정점이 b개, 간선이 a개인 무방향 그래프(undirected graph)가 주어졌을 때, 이 그래프가 오일러 회로(Euler Circuit)를 가지도록 만들기 위해 추가해야 하는 최소 간선 수를 구하는 것이 목표입니다.
예를 들어 다음과 같은 그래프가 입력으로 주어지면,
출력 결과는 1이 됩니다.
오일러 회로의 조건
오일러 회로란 그래프의 모든 간선을 정확히 한 번씩 통과하면서 다시 시작점으로 돌아오는 닫힌 경로입니다. 무방향 그래프에서 오일러 회로가 존재하려면 다음 조건을 만족해야 합니다.
- 그래프가 연결되어 있어야 합니다.
- 모든 정점의 차수(degree, 해당 정점에 연결된 간선의 수)가 짝수여야 합니다.
따라서 차수가 홀수인 정점이 존재한다면, 홀수 차수 정점 두 개를 하나의 간선으로 연결할 때마다 두 정점을 동시에 짝수로 만들 수 있습니다. 즉, 필요한 추가 간선 수는 대략 '홀수 차수 정점의 수 ÷ 2'가 됩니다.
풀이 접근 방법
이 문제는 깊이 우선 탐색(DFS)을 활용하여 해결할 수 있습니다. 알고리즘의 단계는 다음과 같습니다.
- dfs() 함수 정의: 그래프 g, 방문 배열 visit, 홀수 정점 카운터 odd_vert, 차수 배열 degree, 연결 성분 번호 comp, 현재 정점 v를 매개변수로 받습니다.
- 현재 정점 v를 방문 처리합니다(visit[v] := 1).
- 차수가 홀수인 정점이라면 해당 연결 성분의 홀수 정점 개수를 1 증가시킵니다.
- 인접한 모든 정점 u 중 아직 방문하지 않은 정점이 있다면 재귀적으로 dfs()를 호출합니다.
- 메인 로직: n+1개의 빈 리스트로 인접 리스트 g를 초기화하고, 홀수 정점이 없는 성분을 담을 e, 홀수 정점이 있는 성분을 담을 o, 그리고 degree, visit, odd_vert 배열을 준비합니다.
- m개의 간선 정보를 바탕으로 인접 리스트를 채우고 각 정점의 차수를 계산합니다.
- 방문하지 않은 정점을 만날 때마다 새로운 연결 성분으로 간주하고(comp 증가) DFS를 수행합니다.
- 탐색이 끝난 성분에 홀수 정점이 없으면 e에, 하나라도 있으면 o에 추가합니다.
- o가 비어 있고 e의 크기가 1이라면 이미 오일러 회로가 존재하므로 0을 반환합니다.
- o가 비어 있다면 분리된 성분들을 연결하는 데 e의 크기만큼 간선이 필요하므로 e의 크기를 반환합니다.
- e가 비어 있지 않으면 ans에 e의 크기를 더합니다.
- 각 홀수 성분에 대해 odd_vert[i] // 2(정수 나눗셈)만큼 간선 수를 더합니다.
- 최종적으로 ans를 반환합니다.
구현 예제
다음은 위 알고리즘을 파이썬으로 구현한 코드입니다.
def dfs(g, visit, odd_vert, degree, comp, v):
visit[v] = 1
if (degree[v] % 2 == 1):
odd_vert[comp] += 1
for u in range(len(g[v])):
if (visit[u] == 0):
dfs(g, visit, odd_vert, degree, comp, u)
def solve(n, m, s, d):
g = [[] for i in range(n + 1)]
e = []
o = []
degree = [0] * (n + 1)
visit = [0] * (n + 1)
odd_vert = [0] * (n + 1)
for i in range(m):
g[s[i]].append(d[i])
g[d[i]].append(s[i])
degree[s[i]] += 1
degree[d[i]] += 1
ans = 0
comp = 0
for i in range(1, n + 1):
if (visit[i] == 0):
comp += 1
dfs(g, visit, odd_vert, degree, comp, i)
if (odd_vert[comp] == 0):
e.append(comp)
else:
o.append(comp)
if (len(o) == 0 and len(e) == 1):
return 0
if (len(o) == 0):
return len(e)
if (len(e) != 0):
ans += len(e)
for i in range(len(o)):
ans += odd_vert[i] // 2
return ans
b = 3
a = 2
source = [1, 2]
destination = [2, 3]
print(solve(b, a, source, destination))입력
b = 3, a = 2 source = [1, 2] destination = [2, 3]
출력
1
결과 해석
위 예제의 그래프는 정점 1-2와 2-3을 잇는 두 개의 간선을 가집니다. 이때 정점 1과 3의 차수는 1(홀수), 정점 2의 차수는 2(짝수)입니다. 홀수 차수 정점이 2개뿐이므로 이 둘을 연결하는 간선 단 하나만 추가하면 모든 정점의 차수가 짝수가 되어 오일러 회로를 완성할 수 있습니다. 따라서 출력값은 1입니다.