[Python] 백준 1976번 - 여행 가자(2)

문제

• 백준 1976번

최종 코드

import sys
input = sys.stdin.readline

n = int(input())
m = int(input())
L = [i for i in range(n + 1)]


def union(a, b):
    if L[a] != a:
        a = find(a)
    if L[b] != b:
        b = find(b)

    if a != b:
        L[b] = a


def find(a):
    if L[a] == a:
        return a

    root = find(L[a])
    L[a] = root
    return root


for i in range(1, n + 1):
    temp = [0] + list(map(int, input().split()))

    for j in range(1, len(temp)):
        if temp[j] == 1:
            union(i, j)

routes = list(map(int, input().split()))

possible = True
for i in range(len(routes) - 1):
    start = find(routes[i])
    end = find(routes[i + 1])

    if start != end:
        possible = False
        break

if possible:
    print("YES")
else:
    print("NO")

풀이 과정

---

• 이전글

[Python] 백준 1976번 - 여행 가자

• 이전글에서는 해당 문제를 BFS를 이용하여 해결했지만, 서로 연결된 도시들을 그룹으로 생각하고 도시가 연결 되어있는지 여부를 동일 그룹에 속하는지 확인하면 될 것 같아 union-find 알고리즘을 이용하여 다른 방식으로 풀어보았다
• 인접 행렬을 입력 받아 연결 되어있으면 union 연산을 통해 동일 그룹으로 처리하였고, 마지막의 여행 경로의 리스트에서 앞 뒤의 요소가 연결되어있는지 find 연산을 통해 그룹을 알아내어 비교하여 확인하였다
• BFS를 이용할 때보다 로직이 더 단순해져서 풀기 편했다!

틀린 부분 또는 궁금한 점은 댓글로 남겨주세요! 항상 환영합니다!