1976번 여행 가자

문제

https://www.acmicpc.net/problem/1976

1) 플로이드 워셜

그래프 문제는 웬만하면 재밌는듯 👀

최단거리를 구하는 문제는 아니지만 모든 노드에서 다른 모든 노드까지의 연결 여부를 알기 위해 플로이드 워셜을 사용하기로 했다.

여행 계획이 주어졌을 때 단순히 a - b가 직접적으로든 간접적으로든 연결되어 있으면 되기 때문에, 노드간의 연결 관계를 모두 캐싱해놓은 다음에 O(m) 연결 관계 확인하는 게 시간 효율적일 거라 판단했다. F-W dp 테이블 갱신하는 과정은 O(n^3)이지만 n = 200이라 낫밷..?!

코드

from itertools import permutations
import sys
input = sys.stdin.readline

INF = 1e9

n = int(input())
m = int(input())
adj_matrix = [list(map(int, input().split())) for _ in range(n)]

graph = [[INF] * n for _ in range(n)]
for i in range(n):
    for j in range(n):
        if i == j:
            graph[i][j] = 0  # 자기자신
        elif adj_matrix[i][j] == 1:
            graph[i][j] = 1  # 직접적인 연결

# F-W
for k in range(n):
    for a, b in permutations([i for i in range(n) if i != k], 2):
        if a == b:
            continue
        graph[a][b] = min(graph[a][b], graph[a][k] + graph[k][b])

links = list(map(int, input().split()))  # 여행 계획

success = True
for i in range(1, m):
    a, b = links[i - 1] - 1, links[i] - 1
    if graph[a][b] == INF:
        success = False
        break

print("YES" if success else "NO")

2) 유니온 파인드

최근 유니온 파인드 알고리즘 학습해서 새로운 풀이 업뎃 ! (+0422)

- 입력된 인접 행렬에 따라 union 수행
- 연결 관계에 따라 find 수행

접근방식 자체는 위에서 활용한 것보다 훨씬 간단,,

코드

import sys
input = sys.stdin.readline


def find_parent(p, x):
    if p[x] != x:
        p[x] = find_parent(p, p[x])
    return p[x]


def union_parent(p, a, b):
    a = find_parent(p, a)
    b = find_parent(p, b)

    if a < b:
        p[b] = a
    else:
        p[a] = b


n = int(input())
m = int(input())
adj_matrix = [list(map(int, input().split())) for _ in range(n)]

parent = [i for i in range(n)]

for i in range(n):
    for j in range(i, n):
        if adj_matrix[i][j] == 1:
            union_parent(parent, i, j)

links = list(map(int, input().split()))  # 여행 계획

success = True
for i in range(1, m):
    a, b = links[i - 1] - 1, links[i] - 1
    if find_parent(parent, a) != find_parent(parent, b):
        success = False
        break

print("YES") if success else print("NO")

효율성 비교

위: 유니온파인드, 아래: F-W

유니온파인드 승 ✨
아무래도 FW은 DP 테이블 자체를 갱신하는 게 O(n^3)라서..