[BOJ/백준] 1976 여행 가자

import sys
 
sys.setrecursionlimit(1000)
def dfs(node,cnt):
    for next_node,val in enumerate(arr[node]):
        if val and visited[next_node] == 0:
            visited[next_node] = cnt
            dfs(next_node,cnt)
 
 
 
 
 
N = int(input())
M = int(input())
arr = [list(map(int,input().split())) for _ in range(N)]
 
tour_list = list(map(int,input().split()))
 
visited = [0]*N
cnt = 1
for i in range(N):
    if visited[i] == 0:
        visited[i] = cnt
        dfs(i,cnt)
        cnt += 1
 
result = 'YES'
init = visited[tour_list[0]-1]
for city in tour_list[1:]:
    if visited[city -1] != init:
        result = 'NO'
print(result)

첫 풀이 방식은 다음과 같았다.

 

DFS를 통해 모두 연결이 된대를 같은 cnt로 표시를 했다. 그런데 만약에 같은 cnt가 아니라면 tour_list에서 한번에 갈수 없는 곳 이므로 result를 No로 출력했다.

 

 

import sys
input = sys.stdin.readline
 
def union(A,B):
    x = find_parent(A)
    y = find_parent(B)
    if x > y:
        x,y = y,x
    make_set[y] = x
    for i in range(N+1):
        if make_set[i] != i:
            make_set[i] = find_parent(make_set[i])
 
def find_parent(ind):
    if make_set[ind] == ind:
        return ind
     
    return find_parent(make_set[ind])
N = int(input())
M = int(input())
edges = []
for i in range(N):
    graph_list = list(map(int,input().split()))
    for j in range(N):
        if graph_list[j] == 1:
            edges.append((i+1,j+1))
 
tour_list = list(map(int,input().split()))
make_set = [i for i in range(N+1)]
 
for edge in edges:
    node_a,node_b = edge
    if find_parent(node_a) != find_parent(node_b):
        union(node_a,node_b)
 
init_value = make_set[tour_list[0]]
result = 'YES'
for city in tour_list:
    if init_value != make_set[city]:
        result = 'NO'
        break
print(result)

좀 더 원론적인 union find를 해서 같은 집합인지 아닌지 판별을 했다.

 

그리고 난뒤에 같은 집합이 아니면 No를 출력하게 했다.