(백준/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. 구현
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <iostream> | |
#include <algorithm> | |
#include <vector> | |
using namespace std; | |
int getParent(vector<int>& parent, int a) | |
{ | |
if (parent[a] == a) return a; | |
return parent[a] = getParent(parent, parent[a]); | |
} | |
void Union(vector<int>& parent, int a, int b) | |
{ | |
a = getParent(parent, a); | |
b = getParent(parent, b); | |
if (a < b) parent[b] = a; | |
else parent[a] = b; | |
} | |
int Find(vector<int>& parent, int a, int b) | |
{ | |
a = getParent(parent, a); | |
b = getParent(parent, b); | |
if (a == b) return 1; | |
else return 0; | |
} | |
int main() | |
{ | |
int n, m; | |
cin >> n >> m; | |
vector<int> arr; | |
arr.resize(n + 1); | |
for (int i = 1; i <= n; ++i) | |
{ | |
arr[i] = i; | |
} | |
for (int i = 1; i <= n; ++i) | |
{ | |
for (int j = 1; j <= n; ++j) | |
{ | |
int a; | |
cin >> a; | |
if (a) | |
{ | |
Union(arr, i, j); | |
} | |
} | |
} | |
vector<int> plan; | |
for (int i = 1; i <= m; ++i) | |
{ | |
int a; cin >> a; | |
plan.push_back(a); | |
} | |
for (int i = 0; i < m-1; ++i) | |
{ | |
if (arr[plan[i]] != arr[plan[i + 1]]) | |
{ | |
cout << "NO"; | |
return 0; | |
} | |
} | |
cout << "YES"; | |
return 0; | |
} |
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 |
@핑크코냥 :: 핑크코냥
안 하는 것 보다 낫겠지
포스팅이 좋았다면 "좋아요❤️" 또는 "구독👍🏻" 해주세요!