백준 16168 퍼레이드 Python

🐸 문제 정보

16168번: 퍼레이드

 

🤖 알고리즘

오일러 경로 (유니온 파인드 + 그래프 탐색)

 

⏱️ 풀이 시간

60m+ (중간에 오일러 경로의 조건을 찾아보느라 길어졌다.)

 

📝 풀이

오일러 경로는 한 붓 그리기와 같다.

오일러 경로가 성립하기 위해서는 총 두가지 조건에 만족해야한다.

1. 모든 정점이 연결되어있어야한다.
2. 차수(연결된 노드 수)의 두 규칙 중 한개를 만족해야한다.
   • 모든 노드의 차수가 짝수이다.
   • 두 노드의 차수는 홀수, 나머지 노드는 짝수이다.

이 조건을 찾고 공부하느라 조금 늦어졌다ㅠㅠ

우선 모든 정점이 연결되어있는지 찾기 위해 유니온 파인드를 사용했고, 차수 규칙의 경우 일반 구현으로 풀었다.

 

🧑‍💻 나의 답

# pypy3

import sys
input = sys.stdin.readline

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

def union(a, b):
    a = find(a)
    b = find(b)
    if a < b:
        parent[b] = a
    else:
        parent[a] = b

v, e = list(map(int, input().rstrip().split()))
graph = [[] for _ in range(v + 1)]
parent = [i for i in range(v + 1)]
for _ in range(e):
    a, b = list(map(int, input().rstrip().split()))
    if find(a) != find(b): union(a, b)
    graph[a].append(b)
    graph[b].append(a)


# 모두 연결되어있고, 차수 규칙에 맞아야함
temp = find(parent[1])
if not all(find(el) == temp for el in parent[1:]): # 연결되지 않은 경우
    print('NO')
    exit()
nodes = [len(node) % 2 for node in graph[1:]]
if all(el == 0 for el in nodes) or (nodes.count(1) == 2): # 차수 규칙
    print('YES')
else:
    print('NO')