(백준/c++) 1976번 - 여행 가자📃 coding test/◽ 백준2022. 2. 15. 21:05
Table of Contents
728x90
1976번: 여행 가자
동혁이는 친구들과 함께 여행을 가려고 한다. 한국에는 도시가 N개 있고 임의의 두 도시 사이에 길이 있을 수도, 없을 수도 있다. 동혁이의 여행 일정이 주어졌을 때, 이 여행 경로가 가능한 것인
www.acmicpc.net
1. 사용한 알고리즘: 서로소 알고리즘(유니온 파인드)
2. 풀이: 문제에 나와 있는 거 문장을 보면 `같은 도시를 여러 번 방문하는 것도 가능하다.`라고 나와 있다. 여행 계획의 시작 지점을 시작으로 경로를 가기 위한 edge가 이어져 있다면 어떤 방법으로든 여행 계획을 한 번씩 들려서 목적지까지 도달할 수 있다. 밑에는 백준 문제에 예시를 그림으로 표현하고 배열의 인덱스에 맞는 value 값을 표현한 것이다.
이처럼 여행 계획의 경로를 가리키는 value가 모두 같은 값일 때 목적을 달성할 수 있고 value가 하나라도 다르면 목적을 달성할 수 없다.
3. 구현
728x90
'📃 coding test > ◽ 백준' 카테고리의 다른 글
| (백준/c++) 24479 - 알고리즘 수업 - 깊이 우선 탐색 1 (0) | 2022.06.02 |
|---|---|
| (백준/c++) 17472번 - 다리만들기 (0) | 2022.05.25 |
| (백준/c++)20040번 - 사이클 게임 (0) | 2022.02.15 |
| (백준/c++)1780번 - 종이의 개수 (0) | 2022.01.18 |
| (백준/c++) 5430번 - AC (0) | 2022.01.17 |
@핑크코냥 :: 핑크코냥
안 하는 것 보다 낫겠지
포스팅이 좋았다면 "좋아요❤️" 또는 "구독👍🏻" 해주세요!
