[C++] 여행 계획
1. 문제
한울이가 사는 나라에는 N개의 여행지가 있으며, 각 여행지는 1 ~ N번까지의 번호로 구분됩니다. 또한 임의의 두 여행지 사이에는 두 여행지를 연결하는 도로가 존재할 수 있습니다. 이때, 여행지가 도로로 연결되어 있다면 양방향으로 이동이 가능하다는 의미입니다. 한울이는 하나의 여행 계획을 세운 뒤에 이 여행 계획이 가능한지의 여부를 판단하고자 합니다. 예를 들어 N = 5이고, 다음과 같이 도로의 정보가 주어졌다고 가정합시다.
- 1번 여행지 - 2번 여행지
- 1번 여행지 - 4번 여행지
- 1번 여행지 - 5번 여행지
- 2번 여행지 - 3번 여행지
- 2번 여행지 - 4번 여행지
2. 입력
- 첫째 줄에 여행지의 수 N과 여행 계획에 속한 도시의 수 M이 주어집니다.
(1 ≤ N, M ≤ 500)
- 다음 N개의 줄에 걸쳐 N X N 행렬을 통해 임의의 두 여행지가 서로 연결되어 있는지의 여부가 주어집니다. 그 값이 1이라면 서로 연결되었다는 의미이여, 0이라면 서로 연결되어 있지 않다는 의미입니다.
- 마지막 줄에 한울이의 여행 계획에 포함된 여행지들의 번호들이 주어지며 공백으로 구분합니다.
3. 출력
첫째 줄에 한울이의 여행 계획이 가능하다면 YES를, 불가능하다면 NO를 출력합니다.
4. 풀이
- 여행 계획에 포함된 도시들이 서로 연결되어 있는지
=(같은 부모를 가지는지)
확인하면 된다. - 부모를 모두 자기 자신으로 초기화 한다.
N X N
배열을 입력받으면서 서로 연결되어 있다면union
연산을 한다.- 여행 계획을 입력 받은 후 도시들의 부모가 같은 지 확인한다.
5. 첫 코드에서 수정한 점
- 배열을 저장할 필요가 없어서 배열을 없애버렸다.
6. 소스
#include <iostream>
#include <vector>
using namespace std;
int n, m;
int parent[501];
int findParent(int x) {
if(parent[x] == x) return x;
else return findParent(parent[x]);
}
void unionParent(int a, int b) {
a = findParent(a);
b = findParent(b);
if(a < b) parent[b] = a;
else parent[a] = b;
}
int main() {
cin.tie(NULL);
ios_base::sync_with_stdio(false);
cin>>n>>m;
for (int i = 0; i < n; i++) {
parent[i] = i;
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
int x;
cin>>x;
if (x==1) {
unionParent(i+1, j+1);
}
}
}
vector<int> plan;
for (int i = 0; i < m; i++) {
int x;
cin>>x;
plan.push_back(x);
}
bool answer = true;
for (int i = 0; i < m-1; i++) {
if (findParent(i) != findParent(i+1)) {
answer = false;
break;
}
}
if (answer) cout<<"YES";
else cout<<"NO";
}
Author And Source
이 문제에 관하여([C++] 여행 계획), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@e7838752/tripPaln저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)