백준 1976번 : 여행 가자 in Python

1976번: 여행 가자

 

www.acmicpc.net

이 문제는 도시들이 정점으로 주어진 그래프에 대해 여행 계획이 주어진 경우 그래프 내 간선을 통해 해당 여행 계획을 실천할 수 있는지를 묻는 문제이다.

이를 달리 해석하면 여행 계획 내 도시들이 그래프 내에서 모두 연결되어 있는지를 묻는 문제로, 이는 그래프 탐색을 통해 여행 계획 내 정점들이 모두 연결되어 있는지를 확인함으로써 해결할 수 있다. 즉, 우선 여행 계획 내 한 도시에 대해 DFS나 BFS를 실행한 뒤에, 여행 계획 내 나머지 도시들을 방문했었는지를 검사하면 된다.

그러나 이 문제는 다른 방식으로도 해결할 수 있는데, 바로 분리 집합을 이용하는 것이다. 우선 각 도시에 대해 그 도시를 유일한 원소로 가지는 집합을 만든다. 그 다음 만약 두 도시가 간선으로 이어져 있는 경우에 두 도시가 들어있는 집합을 합한다. 그러면 각 도시가 속해 있는 집합의 모든 도시들은 해당 도시와 연결되어 있기 때문에 여행이 가능하다. 반면에 그 집합에 속하지 않는 다른 도시들은 해당 도시와 연결되어 있지 않아 여행이 불가능하다.

이를 구현하는 것은 이전의 집합의 표현 문제와 매우 유사하다. 다만 집합을 합치는 경우가 두 도시가 서로 연결되어 있을 때이고, 마지막에 여행 계획을 점검할 때 find 함수를 모든 도시에 적용해 그 결과가 모두 같은지를 검사한다는 점에서 약간의 차이가 있다. 

백준 1717번 : 집합의 표현 in Python

1717번: 집합의 표현 www.acmicpc.net 이 문제는 집합을 코드 상에서 어떻게 표현하는지에 관한 문제이다. 여기서 집합을 사용하는 목적은 임의의 두 원소가 주어졌을 때 두 원소가 들어있는 집합을 합한다던가(합..

wanna-be-developer-yjh.tistory.com

이를 코드로 구현하면 다음과 같다.

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**5)

N = int(input())
M = int(input())
def find(u):
    if parent[u] == u: return u
    parent[u] = find(parent[u])
    return parent[u]
def union(u, v):
    root_u = find(u)
    root_v = find(v)
    parent[root_u] = root_v
parent = [i for i in range(N+1)]
for i in range(N):
    arr = list(map(int, input().split()))
    for j in range(N):
        # 두 도시가 서로 연결되어 있는 경우 두 도시에 대해 union 함수를 적용한다.
        if arr[j] == 1:
            union(i+1, j+1)
travel = list(map(int, input().split()))
# 여행 계획이 실천 가능한지를 나타내는 변수
possible = True
for i in range(M-1):
    # 여행 계획 내 도시들이 같은 집합 안에 있는지를 검사한다.
    if find(travel[i]) != find(travel[i+1]):
        possible = False
        break
if possible: print("YES")
else: print("NO")