풀이
N + 1개의 집합 1 ~ N에 대해 공통 부모가 다른 경우를 찾아 연결해주면 되는 문제다.
우선, 입력으로 두 집합을 입력받아 union해주자.
모든 입력을 받았다면, parents에 자신의 부모 집합의 번호가 적혀있을 것이다.
반복문을 돌며, 부모 집합의 번호가 다르다면 두 집합은 연결되어 있지 않으므로 두 집합을 연결할 수 있도록 번호를 출력해주면 되는 문제다.
소스코드
출처
17352번: 여러분의 다리가 되어 드리겠습니다!
선린월드에는 N개의 섬이 있다. 섬에는 1, 2, ..., N의 번호가 하나씩 붙어 있다. 그 섬들을 N - 1개의 다리가 잇고 있으며, 어떤 두 섬 사이든 다리로 왕복할 수 있다. 어제까지는 그랬다. "왜 다리
www.acmicpc.net
'PS > Baekjoon Online Judge' 카테고리의 다른 글
| [백준 4195] 친구 네트워크 [Java] (0) | 2023.06.29 |
|---|---|
| [백준 1976] 여행 가자 [Java] (0) | 2023.06.29 |
| [백준 1717] 집합의 표현 [Java] (0) | 2023.06.28 |
| [백준 13701] 중복 제거 [Java] (0) | 2023.06.27 |
| [백준 28235] 코드마스터 2023 [Python] (0) | 2023.06.25 |