풀이
이전에 풀었던 문제의 확장판이다.
[백준 17352] 여러분의 다리가 되어 드리겠습니다! [Java]
풀이 N + 1개의 집합 1 ~ N에 대해 공통 부모가 다른 경우를 찾아 연결해주면 되는 문제다. 우선, 입력으로 두 집합을 입력받아 union해주자. 모든 입력을 받았다면, parents에 자신의 부모 집합의 번호
kyr-db.tistory.com
입력에 따라 union을 해주고, 최대 1000개 까지 주어지는 최대 200이하의 도시에 대해 여행계획이 가능한지,
즉 공통 부모가 다르지 않은지 확인하는 문제다.
입력받은 i번째 줄의 j번이 1이라면 i 에서 j는 연결된 도시이다.
마지막에 입력되는 여행 계획은 결국 도시들이 하나로 연결이 되어있는지 여부에 따라 여행 가능 여부가 결정된다.
즉, 공통 부모가 동일하다면 하나로 연결된 도시이며,
공통 부모가 하나라도 다르다면 분리된 도시이기에 여행이 불가능하다.
소스코드
출처
1976번: 여행 가자
동혁이는 친구들과 함께 여행을 가려고 한다. 한국에는 도시가 N개 있고 임의의 두 도시 사이에 길이 있을 수도, 없을 수도 있다. 동혁이의 여행 일정이 주어졌을 때, 이 여행 경로가 가능한 것인
www.acmicpc.net
'PS > Baekjoon Online Judge' 카테고리의 다른 글
| [백준 4375] 1 [Java] (0) | 2023.06.29 |
|---|---|
| [백준 4195] 친구 네트워크 [Java] (0) | 2023.06.29 |
| [백준 17352] 여러분의 다리가 되어 드리겠습니다! [Java] (0) | 2023.06.29 |
| [백준 1717] 집합의 표현 [Java] (0) | 2023.06.28 |
| [백준 13701] 중복 제거 [Java] (0) | 2023.06.27 |