백준 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

def getParent(x):
    if parent[x]==x:
        return x
    
    parent[x]=getParent(parent[x])
    return parent[x]


def isSameParent(x,y):
    return getParent(x)==getParent(y)


def unionParent(x,y):
    x=getParent(x)
    y=getParent(y)

    if x<y:
        parent[y]=x
    else:
        parent[x]=y


#메인 코드 부분
v,e=map(int,sys.stdin.readline().split())

parent=[i for i in range(v+1)]

edge=[[] for _ in range(v+1)]
for _ in range(e):
    v1,v2=map(int,sys.stdin.readline().split())
    edge[v1].append(v2)
    edge[v2].append(v1)
    
    if not isSameParent(v1,v2):
        unionParent(v1,v2)


# 모든 노드가 다같이 연결되었는지 확인 (공통의 부모를 공유하는지 파악)
base=getParent(1) # 기준: 1번째 노드의 부모로 설정.
for i in range(2, v+1):
    if base!=getParent(i):
        print('NO')
        exit(0)

odd_cnt=0 # 차수가 홀수인 노드 개수 카운트.
for i in range(1,v+1):
    if len(edge[i])%2==1:
        odd_cnt+=1


if odd_cnt==2 or odd_cnt==0:
    print('YES')
else:
    print('NO')

 

 

풀이 및 접근)

- 해당 문제는 오일러 경로에 대해서 모르면 풀기 힘든 문제이다. 오일러 경로란 한붓 그리기 라고 생각하면 된다.

 

- 노드와 간선 정보가 주어졌을 때 오일러 경로를 만들 수 있는지 판별하는 공식이 있다. 다음 두가지 조건 중 하나를 만족하면 오일러 경로를 만들 수 있다.

   

    1. 모든 노드의 차수가 짝수인 경우

    2. 두 노드의 차수만 홀수인 경우

 

- 차수란, 노드에 연결된 간선의 수를 의미한다. 위의 해당 조건 중 하나를 만족하면 오일러 경로를 만들 수 있는지 판단할 수 있다.

 

- 사실 이 문제를 업로드 하는 건, 오일러 경로 때문이 아니라 유니온 파인드에서 실수할 수 있는 부분이 있어서이다. 본인은 모든 연결이 완료되었을 때 부모 리스트인 parent[ ]에 최종 부모가 세팅되어 있을 것이라고 생각했다. 하지만 그것은 특정한 상황에서만 그러하였다.

 

- 다음과 같은 순서대로 간선 정보가 주어졌을 때, 최종 연결을 마친 후에도 4의 부모가 1이 아니라 3이 저장되어 있음을 알 수 있다. 따라서 특정 노드의 부모를 알고 싶을 때는, parent[x]를 통해 접근하는 것이 아니라, getParent(x) 함수를 호출함으로써 접근해야 한다. getParent(x)를 호출해야 비로소 진짜 부모를 알 수 있다.

 

- 해당 상황이 발생하는 이유는, 간선들의 정보가 정렬되지 않았기 때문이다. 만약 간선 정보가 (x,y)로 주어질 때, x로 오름차순 되어있거나 y로 오름차순 되어 있었다면, 이를 만족한다. 왜냐하면 unionParent()를 하는 과정에서 오름차순 된 노드들이 들어오므로 부모가 최소값들을 우선으로 설정된다.

 

- 사고하는 과정에서 당연히 최종 연결 후에 parent[x]와 getParent(x)의 값이 동일할 것이라고 생각했다. 하지만 이러한 허점이 존재했었다. 앞으로 최종 부모를 확인할 때는 getParent(x) 호출을 통해 확인하자.