BOJ 1976 - 여행 가자

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

문제

\(n\)개의 도시 사이의 연결 상태가 인접 행렬로 주어지고 여행 계획에 있는 \(m\)개의 도시가 주어질 때, \(m\)개의 도시를 모두 방문할 수  있는가를 묻는 문제이다.

다시말하면, \(m\)개의 도시가 모두 연결되어있는가를 확인하면 된다.

이 문제는 서로소 집합(Disjoint-Set)으로 간단하게 해결할 수 있다. 각 도시들의 연결 상태만 확인하면 되므로, 연결된 도시들을 집합으로 묶어서 표현한 후 마지막에 주어지는 \(m\)개의 도시들이 모두 같은 집합에 속하는 지 확인하면 정답이기 때문이다.

코드

반응형

• 카카오스토리
• 트위터
• 페이스북

'알고리즘 > 문제 풀이' 카테고리의 다른 글

BOJ 16964 - DFS 스페셜 저지  (0)	2019.03.12
BOJ 11447 - Colby’s Costly Collectibles  (0)	2019.03.11
BOJ 1976 - 여행 가자  (0)	2019.03.08
BOJ 1613 - 역사  (0)	2019.02.24
BOJ 9465 - 스티커  (0)	2019.02.24
BOJ 10472 - 십자뒤집기  (0)	2019.02.23