[Python/파이썬] 백준 17352번 여러분의 다리가 되어 드리겠습니다!

17352번: 여러분의 다리가 되어 드리겠습니다!

 

문제

선린월드에는 N개의 섬이 있다. 섬에는 1, 2, ..., N의 번호가 하나씩 붙어 있다. 그 섬들을 N - 1개의 다리가 잇고 있으며, 어떤 두 섬 사이든 다리로 왕복할 수 있다.

어제까지는 그랬다.

"왜 다리가 N - 1개밖에 없냐, 통행하기 불편하다"며 선린월드에 불만을 갖던 욱제가 다리 하나를 무너뜨렸다! 안 그래도 불편한 통행이 더 불편해졌다. 서로 왕복할 수 없는 섬들이 생겼기 때문이다. 일단 급한 대로 정부는 선린월드의 건축가를 고용해, 서로 다른 두 섬을 다리로 이어서 다시 어떤 두 섬 사이든 왕복할 수 있게 하라는 지시를 내렸다.

그런데 그 건축가가 당신이다! 안 그래도 천하제일 코딩대회에 참가하느라 바쁜데...

입력

첫 줄에 정수 N이 주어진다. (2 ≤ N ≤ 300,000)

그 다음 N - 2개의 줄에는 욱제가 무너뜨리지 않은 다리들이 잇는 두 섬의 번호가 주어진다.

출력

다리로 이을 두 섬의 번호를 출력한다. 여러 가지 방법이 있을 경우 그 중 아무거나 한 방법만 출력한다.

코드

import sys
input = sys.stdin.readline

def find_parent(n, parent):
    if n != parent[n]:
        parent[n] = find_parent(parent[n], parent)
    return parent[n]

def union_parent(a, b, parent):
    a = find_parent(a, parent)
    b = find_parent(b, parent)
    
    if a == b:  # 이미 같은 그래프에 속함
        return
    # 번호가 더 작은 쪽을 부모로
    if a < b:
        parent[b] = a
    else:
        parent[a] = b
        
n = int(input())
parent = [i for i in range(n+1)]
for _ in range(n-2):
    a, b = map(int, input().split())
    union_parent(a, b, parent)
    
for i in range(2, n+1):
    if find_parent(i, parent) != 1:
        print(1, i)
        break

 

전형적인 분리집합 문제이다.

문제의 설명을 읽어보면 섬을 노드들이라고 생각할 때 2개로 나뉜 그래프를 이어줄 간선 아무거나 1개만 구하면 되는 문제이다. 따라서 문제의 입력으로 주어지는 이어진 두 다리의 번호, 즉 연결된 간선 정보들을 이용하여 그래프 정보를 구해서 두 그래프의 루트 노드들을 출력하도록 했다. 더 작은 쪽이 부모 노드로 저장되도록 해놓았기 때문에 1개의 그래프는 무조건 루트 노드가 1일 것이다. 그래서 28번째 줄에서 find_parent(i , parent) == 1인지 확인하는 것이다.

 

처음에는 Python3에서는 시간 초과로 통과가 안되길래

import sys
input = sys.stdin.readline

이거 추가했더니 됐다...