[백준] 1976번 : 여행 가자 - Python(파이썬)

문제

https://www.acmicpc.net/problem/1976

1976번: 여행 가자

 

풀이

• find-union 문제

 

Find-Union 알고리즘

• 초기화 : N개의 원소가 각각의 집합에 포함되어 있도록 초기화
• union : 두 원소가 a, b가 속한 집합 합침
• find : 원소 a가 주어지면 해당 원소가 속한 집합 반환 

 

트리 구조 사용 : 알고리즘 구현

1. 주어진 원소의 갯수만큼 사용하지 않을 값 (-1) 생성
2. 루트 노드의 인덱스 찾음
3. 루트 노드가 다르면 size/height가 더 작은 것을 찾아 큰 것에 더해줌
4. 작은 것의 인덱스를 큰 것으로 바꿔줌

 

예제 : Find-Union 알고리즘

/* 초기화 */
int root[MAX_SIZE];
for (int i = 0; i < MAX_SIZE; i++)
    parent[i] = i;

/* find(x): 재귀 이용 */
int find(int x) {
    // 루트 노드는 부모 노드 번호로 자기 자신을 가진다.
    if (root[x] == x) {
        return x;
    } else {
        // 각 노드의 부모 노드를 찾아 올라간다.
        return find(root[x]);
    }
}

/* union(x, y) */
void union(int x, int y){
    // 각 원소가 속한 트리의 루트 노드를 찾는다.
    x = find(x);
    y = find(y);

    root[y] = x;
}
https://gmlwjd9405.github.io/2018/08/31/algorithm-union-find.html

 

코드

#문제 : https://www.acmicpc.net/problem/1976

import sys

def find(x):#x의 루트노드찾기
    if P[x]<0:
        return x
    else:
        y=find(P[x])
        P[x]=y
        return P[x]
 
def union(x,y):
    x_root=find(x)
    y_root=find(y)
    if x_root != y_root:#루트노드가 같지 않으면
        P[y_root]=x_root#루트노드를 다른 루트노드에 붙여준다.
 
 
#전체 도시수 
N=int(sys.stdin.readline())
#주어진 원소 갯수 만큼 사용하지 않을 값 -1 생성
P=[-1]*(N+1)  #도시가 1부터 시작해서 (N+1)로 통일
#여행 계획에 속한 도시 수
M=int(sys.stdin.readline())

for i in range(N):
    connection=list(map(int,sys.stdin.readline().split()))
    for j in range(i+1,N): #양방향
        if connection[j]: #짝
            union(i+1,j+1)
 
check=True
t_route=list(map(int,sys.stdin.readline().split())) #여행 경로
t_root=find(t_route[0])
for i in range(M):#루트 동일?
    if find(t_route[i])!=t_root:
        check=False
        break
 
if check:
    print("YES")
else:
    print("NO")