[Python/파이썬] 백준 16168번 퍼레이드

16168번: 퍼레이드

 

문제

종우는 18학번을 대표하여 중앙대학교 개교 100주년 기념 퍼레이드의 경로 선정 위원으로 선정되었다. 퍼레이드의 경로는 일정한 지점들과 두 지점을 연결하는 연결 구간으로 이루어져 있다. 종우는 모든 지점을 지나면서 모든 연결 구간들을 지나고 싶어한다.

하지만 같은 연결 구간을 두 번 이상 지날 경우 그 구간의 주민들이 민원을 제기하게 된다. 단, 같은 지점은 두 번 이상 지나도 된다.

민원을 받지 않으면서 모든 구간을 지나도록 퍼레이드를 만들고 싶은 종우를 위한 프로그램을 작성해보도록 하자.

입력

첫 번째 줄에 지점의 개수 V, 연결 구간의 개수 E가 주어진다. (1 ≤ V ≤ E ≤ 3000) 이후 E개의 줄에 걸쳐 각 연결 구간이 연결하는 두 지점의 번호 Va, Vb가 공백을 사이에 두고 주어진다. (1 ≤ Va, Vb ≤ V, Va ≠ Vb)

서로 다른 두 연결 구간 (Va1, Vb1), (Va2, Vb2) 에서 Va1 = Va2 & Vb1 = Vb2 인 경우는 존재하지 않으며, 임의의 지점에 적어도 하나의 연결 구간이 연결되어 있음이 보장된다.

출력

종우가 원하는 노선을 만들 수 있다면 YES, 아니면 NO를 출력한다.

코드

import sys
input = sys.stdin.readline

def find(a):
    if parent[a] != a:
        parent[a] = find(parent[a])
    return parent[a]

def union(a, b):
    a = find(a)
    b = find(b)

    if a == b:
        return
    if a <= b:
        parent[b] = a
    else:
        parent[a] = b

v, e = map(int, input().split())
parent = [i for i in range(v+1)]
degree = [0] * (v+1)
for _ in range(e):
    a, b = map(int, input().split())
    union(a,b)
    degree[a] += 1
    degree[b] += 1

# 루트 노드 정보 다시 한 번 업데이트
for i in range(1, v+1):
    find(i)

# 모두 같은 그래프에 속해 있는지 확인
if len(set(parent[1:])) != 1:
    print("NO")
    exit()

# 각 정점의 차수 확인(차수가 홀수개인 정점이 0개이거나 2개이어야 가능)
odd_degree = 0  # 차수가 홀수인 정점 개수
for i in range(1, v+1):
    if degree[i] % 2 == 1:
        odd_degree += 1
print("YES" if (odd_degree < 4) else "NO")

 

한붓그리기, 즉 오일러 경로를 만들 수 있는지 확인해보면 되는 문제였다.

이를 위해서는 2가지를 확인해보면 되는데

• 모든 정점이 같은 그래프에 속해있는가
• 차수가 홀수개인 정점이 0개 또는 2개인가

모든 정점이 같은 그래프에 속해있는지 확인해보기 위해서 분리집합 알고리즘을 사용하였다. 같은 그래프에 속해있다면 모두 같은 루트 노드를 가질 것이므로 모든 정점의 parent 배열의 값이 모두 같을 것이다. 처음에는 루트 정보를 다시 한 번 업데이트해주지 않아서 97퍼에서 계속 틀렸다. 

한붓그리기가 가능하려면 차수(정점으로 연결된 간선의 개수)가 홀수 개인 정점이 0개이거나 2개이어야 한다. 2개인 경우 홀수개인 정점이 시작점이 되어야 한다.

예제 1이 차수가 홀수 개인 정점이 2개인 경우이다. 시작점과 끝점을 제외한 나머지 정점은 들어갔다가 나가는 과정이 필요하므로 정점이 짝수 개가 필요한 것이다.

차수가 홀수개인 정점이 홀수 개인 경우는 없다. 그래서 홀수 개인 정점의 개수가 4개보다 작은지 확인해주면 된다.