051 여행 가자

첫번째 코드

 

2차원 행렬로 유니온 파인드를 적용해야하나 그건 어떻게 하는거지? 고민을 했는데

책을 참고하고 코드를 작성했을 때

유니온 파인드를 어떻게 사용할 것인지 생각을 잘 해야할 것 같다!

 

문제는 행렬이지만

유니온 파인드로 결국 부모 노드를 찾는 것이므로 행렬일 필요가 없다!

 

import sys
input = sys.stdin.readline

n = int(input())
m = int(input())

city= [[0 for j in range(n+1)] for i in range(n+1)]

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

route = list(map(int, input().split()))
route.insert(0, 0)

parent = []
for i in range(n+1):
    parent.append(i)

def find(a):
    if a == parent[a]:
        return a
    else:
        parent[a] = find(parent[a])
        return parent[a]

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

for i in range(1, n+1):
    for j in range(1, n+1):
        if city[i][j] == 1:
            union(i, j)

index = find(route[1])
isconnected = True

for i in range(2, len(route)):
    if index != find(route[i]):
        isconnected = False
        break

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

 

통과

find와 union 함수 구성은 익숙해지고 있지만 아직 문제를 풀 정도로 유연하게 사용하지는 못하는 느낌이다!

---

링크

https://github.com/ornni/programmers/tree/main/%EB%B0%B1%EC%A4%80/Gold/1976.%E2%80%85%EC%97%AC%ED%96%89%E2%80%85%EA%B0%80%EC%9E%90

programmers/백준/Gold/1976. 여행 가자 at main · ornni/programmers