반응형
문제
https://www.acmicpc.net/problem/1976
1976번: 여행 가자
동혁이는 친구들과 함께 여행을 가려고 한다. 한국에는 도시가 N개 있고 임의의 두 도시 사이에 길이 있을 수도, 없을 수도 있다. 동혁이의 여행 일정이 주어졌을 때, 이 여행 경로가 가능한 것인
www.acmicpc.net
풀이
유니온 파인드 알고리즘으로 풀이할 수 있는 문제입니다.
https://dev-mandos.tistory.com/296
[알고리즘] 유니온 파인드(Union-Find) (Swift)
유니온 파인드 두 노드가 서로 같은 그래프에 속하는지 판별하는 알고리즘 서로소 집합, Disjoint-Set 알고리즘이라고도 불림 부모노드를 찾는 Find 연산, 노드를 합치는 Union 연산으로 이루어져있음
dev-mandos.tistory.com
인접행렬을 확인하여 i와 j를 합집합 연산을 해 노드를 연결시켜 줍시다.
마지막 줄에 여행 계획이 주어진 도시들에 대해 부모 노드를 찾아주고, 부모 노드가 모두 같다면
여행이 가능한 경우입니다.
소스코드
후기
유니온 파인드 문제에 익숙하지 않았는데, 이런 방식으로 활용할 수 있다고 깨달았습니다.
반응형
'PS > 백준' 카테고리의 다른 글
| [BOJ] 백준 20040 사이클 게임 (Swift) (0) | 2023.05.16 |
|---|---|
| [BOJ] 백준 4195 친구 네트워크 (Swift) (0) | 2023.05.16 |
| [BOJ] 백준 1717 집합의 표현 (Swift) (1) | 2023.05.16 |
| [BOJ] 백준 4803 트리 (Swift) (0) | 2023.05.16 |
| [BOJ] 백준 1991 트리 순회 (Swift) (0) | 2023.05.15 |
