Search

여행 계획

문제 : 여행 계획

1976번: 여행 가자
첫 줄에 도시의 수 N이 주어진다. N은 200이하이다. 둘째 줄에 여행 계획에 속한 도시들의 수 M이 주어진다. M은 1000이하이다. 다음 N개의 줄에는 N개의 정수가 주어진다. i번째 줄의 j번째 수는 i번 도시와 j번 도시의 연결 정보를 의미한다. 1이면 연결된 것이고 0이면 연결이 되지 않은 것이다. A와 B가 연결되었으면 B와 A도 연결되어 있다.
https://www.acmicpc.net/problem/1976

풀이

해결에 필요한 핵심 아이디어: 서로소 집합 알고리즘

•
서로소 집합 알고리즘
◦
트리 자료 구조를 활용하는 서로소 집합 자료구조 사용,
◦
서로 연결된 도시들을 union 연산을 이용하여 루트 도시 통일
◦
find 연산을 통해 도시들의 루트 도시를 파악하여 주어진 계획의 가능여부 확인
→ 주어진 계획의 도시들이 모두 같은 루트를 가지고 있다면 OK
풀이

나동빈님 컨텐츠를 이용하시면 더 많고 자세한 내용을 얻을 수 있습니다.

Made with