[알고리즘] 백준 1976 여행 가자

백준 1976 여행 가자

 

이 문제를 처음 보자마자 든 생각은 "경로 문제니깐 경로 알고리즘을 생각해야겠다." 입니다.

그래서 문제 조건을 파악을 하고 

 

# N은 200이하 M은 1000이하
# 어떠한 경로가 더 큰 범주다. 내가 여행 하려고 하는 루트는 작은 범주
# N이 200인데 그냥 플로이드 와샬로 모든 경로 훑으면 되지 않나?

 

이러한 조건을 생각을 하고 플로이드 와샬로 풀었습니다.

그렇지만 다른 사람들의 풀이를 봤을 때, 내가 방향성이 잘못됐구나. 라고 깨달았습니다.

 

기존의 풀이

import sys

# N은 200이하 M은 1000이하
# 어떠한 경로가 더 큰 범주다. 내가 여행 하려고 하는 루트는 작은 범주
# N이 200인데 그냥 플로이드 와샬로 모든 경로 훑으면 되지 않나?

inf = 2147000000
N = int(sys.stdin.readline())
M = int(sys.stdin.readline())
lists = []

for i in range(N):
    row = list(map(int, sys.stdin.readline().split()))
    row = [inf if x == 0 else x for x in row]
    row[i] = 0
    lists.append(row)

travelRoute = list(map(int, sys.stdin.readline().split()))

# 플로이드 와샬
for k in range(N):
    for i in range(N):
        for j in range(N):
            if lists[i][j] > lists[i][k] + lists[k][j]:
                lists[i][j] = lists[i][k] + lists[k][j]
                
for i in range(M-1):
    if lists[travelRoute[i]-1][travelRoute[i+1]-1] == inf:
        print("NO")
        break
else:
    print("YES")

 

이 문제의 핵심은 여행 경로가 도시가 연결된 무수히 많은 루트 안에 포함이 되느냐 아니냐를 판가름 해주면 되는 문제입니다.

특정 루트에 포함 되느냐 아니냐를 판가름해주는 대표적인 알고리즘은 크루스칼, 유니온 파인드 등이 있습니다.

 

 

더 나은 풀이 (유니온 파인드)

import sys


def find_parent(a):
    if parent_list[a] != a:
        parent_list[a] = find_parent(parent_list[a])
    return parent_list[a]

def union(a,b):
    a = find_parent(a)
    b = find_parent(b)
    if a >= b:
        parent_list[a] = b
    else:
        parent_list[b] = a
        
N = int(sys.stdin.readline())
M = int(sys.stdin.readline())
parent_list = [i for i in range(N+1)]

for i in range(N):
    temp = list(map(int, sys.stdin.readline().split()))
    for j in range(N):
        if temp[j] == 1:
            union(i+1, j+1)

travelRoute = list(map(int, sys.stdin.readline().split()))
start = travelRoute[0]
for i in range(1,M):
    if find_parent(start) != find_parent(travelRoute[i]):
        print("NO")
        break
else:
    print("YES")