[BOJ] Q1976 여행 가자

[BOJ] Q1976 여행 가자

Question

Language: Python

Difficulty: Gold 4

해당 문제는 주어진 간선의 정보를 토대로 특정 노드 2개 사이에 경로가 존재하는 지 여부를 판단하는 문제이다. 이러한 유형의 문제는 플로이드 워샬 알고리즘을 통해 모든 노드 간에 연결성을 파악할 수 있고, 유니온 파인드를 통해 서로 연결된 component 내에 존재하는 지 여부를 판단할 수 있다.

Solution 1

플로이드 워샬을 활용한 풀이

from math import inf
def solution():
    for i in range(n):
        for j in range(n):
            if graph[i][j] == 0 and i!=j:
                graph[i][j]=inf
                
    for k in range(n):
        for i in range(n):
            for j in range(n):
                graph[i][j]=min(graph[i][j],graph[i][k] + graph[k][j])
    
    for index in range(m-1):
        if graph[travel_route[index]][travel_route[index+1]] != inf:
            continue
        print("NO")
        break
    else: 
        print("YES")

if __name__ == "__main__":
    n=int(input())
    m=int(input())
    graph=[list(map(int,input().split())) for _ in range(n)]
    travel_route=list(map(lambda x: int(x)-1,input().split()))

    solution()

Solution 2

유니온 파인드를 활용한 풀이

from math import inf
def find_parent_compressed(parents,x):
    if x != parents[x]:
        parents[x]=find_parent_compressed(parents,parents[x])
    return parents[x]

def union_parents(parents,x,y):
    pre_x=find_parent_compressed(parents,x)
    pre_y=find_parent_compressed(parents,y)

    if pre_y<pre_x:
        parents[pre_y]=pre_x
    else:
        parents[pre_x]=pre_y
    

def solution():
    parents=[i for i in range(n)]

    for i in range(n):
        for j in range(n):
            if graph[i][j]==1:
                if find_parent_compressed(parents,i) != find_parent_compressed(parents,j):
                    union_parents(parents,i,j)
    
    for i in range(n):
        find_parent_compressed(parents,i)
        
    parent=parents[travel_route[0]]

    for i in range(1,m):
        if parents[travel_route[i]] != parent:
            print("NO")
            break
    else:
        print("YES")

if __name__ == "__main__":
    n=int(input())
    m=int(input())
    graph=[list(map(int,input().split())) for _ in range(n)]
    travel_route=list(map(lambda x: int(x)-1,input().split()))

    solution()