[알고리즘 문제 풀이][Union-Find] 백준 13383번 - Oil

한붓 그리기 + Union Find 문제

 

백준 13383 Oil 문제의 풀이 방법을 정리한 내용입니다.

저는 문제를 파악하는데 시간이 걸렸어서 다른 분들을 위해 풀고 나서 정리해두었습니다. 도움이 되길 바랍니다.

 

- 문제 설명: 13383번: Oil (acmicpc.net)

 

최대 100개의 집이 주어집니다.

각 집 사이에 z 개만큼의 기름 자국이 남아있습니다.

기름 자국이 남았다는 것은 두 집 사이를 한 번 지나갔다는 것을 의미합니다.

문제에서 주어진 기름 자국들을 보고 Mike 씨 한 명이 다 지나다닌 것이 맞는지 맞추는 문제입니다.

 

- 문제 풀이:

Mike 한 명이 모든 집을 왔다갔다 하려면 한붓 그리기 문제처럼 풀 수 있을 것입니다.

또한 왔다갔다한 집들을 합쳐줘야하기 때문에 Union-Find 도 필요합니다.

 

정리하면, Union-Find 로 기름 자국들로 연결된 집들을 모두 한 그룹으로 묶습니다.

이런 그룹이 여러 개 등장한다면 Mike 씨 외에 누군가 기름 자국을 그리고 있다는 뜻이 될 것입니다.

또한, 기름 자국들로 연결된 집을 한붓 그리기 할 수 있는지 알아야합니다.

한붓 그리기를 판단하는 규칙은 간단합니다. 각 꼭짓점에 연결된 선의 개수가 홀수인 것만 세었을 때 0개 혹은 2개가 나오면 됩니다.

 

- 코드 (Python): 

import sys
input=sys.stdin.readline

def find(p):
    global parents 
    while p!=parents[p]: 
        p=parents[p] 
    return p 

for t in range(int(input())): 
    n_house=int(input()) 
    nums=list(map(int,input().split()))
    n=nums[0] 
    edge=[0]*n_house 
    parents=[0]*n_house
    child_cnt=[1]*n_house
    for i in range(n_house):
        parents[i]=i
    for i in range(1,n*3+1,3): 
        x,y,z=nums[i],nums[i+1],nums[i+2]
        edge[x]+=z 
        edge[y]+=z 
        p1=find(x) 
        p2=find(y) 
        parents[p1]=p2
        child_cnt[p2]+=child_cnt[p1]
        child_cnt[p1]=0
        parents[x]=p2 
        parents[y]=p2

    pcnt=0
    for i in range(n_house): 
        if child_cnt[i]>1: 
            pcnt+=1 
    if pcnt>1:
        print("no")
    else: 
        odd=0 
        for i in range(n_house): 
            if edge[i]%2: 
                odd+=1 
        if odd==0 or odd==2: 
            print("yes") 
        else: 
            print("no")

 

백준의 Union Find 문제들은 대개 입력 라인이 매우 많이 주어지기 때문에 input 대신 sys.stdin.readline 으로 빠르게 입력을 받을 수 있도록 하였습니다.

위의 코드는 Union 함수를 별도로 구현하지 않고 for 문에 합쳐서 구현하였습니다.

 

- 실수 포인트 & 반례:

문제의 예제 외에 필요한 반례는 없었습니다