1976

날짜 : 2023. 02. 22

사용 언어 : python

 

문제

 

 

코드

import sys
sys.setrecursionlimit(10**6)

n = int(sys.stdin.readline()) # 도시의 개수 (200 이하)
m = int(sys.stdin.readline()) # 여행 계획에 속한 도시의 개수 (1000 이하)
parent = [i for i in range(n+1)] # 각 노드별 부모 테이블


def find(node): # 노드의 부모 찾기
    if node == parent[node]: # 해당 노드가 부모 노드면 리턴
        return node
    p = find(parent[node]) # 해당 노드에 대한 부모 찾기(거슬러 올라감)
    parent[node] = p  # 부모 노드 갱신
    return parent[node]  # 부모노드 리턴


def union(a, b):  # a 집합과 b 집합 합치기
    # 각 노드의 부모 찾기
    a = find(a)
    b = find(b)
    
    if a == b: # 동일한 집합인 경우
        return
    if a < b:  # a의 부모 < b의 부모 -> b의 부모가 a 부모 밑으로 들어감
        parent[b] = a
    else:  # 반대
        parent[a] = b


for i in range(1, n+1):  # i 번째 도시
    link = list(map(int, sys.stdin.readline().split()))  # 연결정보 입력
    for j in range(1, len(link) + 1):  # 연결정보에 대해서 탐색
        if link[j-1] == 1: # 연결되어 있다면
            union(i, j) # 합치기

plan = list(map(int, sys.stdin.readline().split()))  # 여행 계획
res = set([find(i) for i in plan])
if len(res) != 1: print('NO')
else: print('YES')

 

 

풀이

- 분리집합을 이용해 각 노드별 parent를 기록하고, 노드끼리의 parent를 비교하면서 최신화한다.

- 또한 for문을 이용한 연결정보를 탐색하면서 집합이 연결되었다면 union을 이용해 합침으로써 parent 테이블을 최신화한다.

- 마지막에는 여행계획을 입력받고 각 계획마다의 parent를 탐색, 값이 1인 경우(서로 같은 집합) yes, 아니라면 no를 출력한다.

 

 

알게된 점

- 각 노드별로 연결정보를 전부 입력받고 반복문을 통해 연결정보를 계속 최신화하는 방식으로 코드를 짜려고 했지만 너무 비효율적이었다.

- 그래서 하단 알고리즘 분류르 참고, 분리집합이라는 알고리즘을 활용한 문제라는 것을 알게 되었다.

- 구글링한 결과 해당 알고리즘을 공부할 수 있었고 이를 활용해 문제를 해결했다.

 

 

참고 사이트

- https://deep-learning-study.tistory.com/590

[백준 파이썬] 1976번 여행가자

- https://blog.naver.com/ndb796/221230967614

17. Union-Find(합집합 찾기)