JOYFUL's Devlog
/
Data Structure & Algorithm
/
여행 계획
Search
Share
여행 계획
문제 : 여행 계획
1976번: 여행 가자
첫 줄에 도시의 수 N이 주어진다. N은 200이하이다. 둘째 줄에 여행 계획에 속한 도시들의 수 M이 주어진다. M은 1000이하이다. 다음 N개의 줄에는 N개의 정수가 주어진다. i번째 줄의 j번째 수는 i번 도시와 j번 도시의 연결 정보를 의미한다. 1이면 연결된 것이고 0이면 연결이 되지 않은 것이다. A와 B가 연결되었으면 B와 A도 연결되어 있다.
풀이
해결에 필요한 핵심 아이디어:
서로소 집합
알고리즘
•
서로소 집합 알고리즘
◦
트리
자료 구조를 활용하는
서로소 집합 자료구조
사용,
◦
서로 연결된 도시들을
union
연산을 이용하여
루트 도시 통일
◦
find
연산을 통해 도시들의
루트 도시를 파악
하여 주어진 계획의 가능여부 확인
→ 주어진 계획의 도시들이
모두 같은 루트
를 가지고 있다면 OK
풀이
나동빈님 컨텐츠를 이용하시면 더 많고 자세한 내용을 얻을 수 있습니다.
나동빈, 『이것이 취업을 위한 코딩테스트다 with 파이썬』, 한빛미디어(2020)
(이코테 2021) 이것이 취업을 위한 코딩 테스트다 with 파이썬