문제
동혁이는 친구들과 함께 여행을 가려고 한다. 한국에는 도시가 N개 있고 임의의 두 도시 사이에 길이 있을 수도, 없을 수도 있다. 동혁이의 여행 일정이 주어졌을 때, 이 여행 경로가 가능한 것인지 알아보자. 물론 중간에 다른 도시를 경유해서 여행을 할 수도 있다. 예를 들어 도시가 5개 있고, A-B, B-C, A-D, B-D, E-A의 길이 있고, 동혁이의 여행 계획이 E C B C D 라면 E-A-B-C-B-C-B-D라는 여행경로를 통해 목적을 달성할 수 있다.도시들의 개수와 도시들 간의 연결 여부가 주어져 있고, 동혁이의 여행 계획에 속한 도시들이 순서대로 주어졌을 때 가능한지 여부를 판별하는 프로그램을 작성하시오. 같은 도시를 여러 번 방문하는 것도 가능하다.
시작하기 앞서 이전에 해결했었던 문제 BOJ_1717과 매우 유사하다.
1717번 문제와 매우 유사하며 가장 중요한 점은 여행의 가능여부를 판단한다는 점이다. 즉, 여행 경로가 한 집합에 포함이 되어있는지를 확인하면 된다. 여기서 나는 다음과 같은 기능을 구현하여 문제풀이를 진행했다.
다음과 같이 구현할 수 있다.
int findParent(int num){
if(num == cities[num]){
return num;
}
else{
return num = findParent(cities[num]);
}
}
여기서 확인할 수 있는 점은 재귀함수
를 이용했다는 것이다.
void Union(int a, int b){ // 그냥 도시의 정보만 입력하면 알아서 최고레벨의 부모를 찾아줌...
if(findParent(a) == findParent(b)){ // 중복확인
return;
}
cities[findParent(a)] = findParent(b);
}
위의 두 함수를 적재 적소에 활용하면 상당히 간단히 해결할 수 있는 문제였다.
//BOJ 1976
#include <iostream>
#include <string>
using namespace std;
int cities[200];
int path[1000];
void Union(int a, int b);
int findParent(int num);
int main(){
ios::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
// 도시의 수 N, 여행계획에 속한 도시의 수 M
int N, M;
cin >> N >> M;
for(int i=0; i<N; i++){
cities[i] = i;
}
// 도시의 연결 정보 입력...
for(int i=0; i<N; i++){
for(int j=0; j<N; j++){
int x;
cin >> x;
if(x == 1){
Union(i,j);
}
}
}
// 도시 여행계확에 속한 도시의 수 M...
int temp;
bool ans = true;
for(int i=0; i<M; i++){
cin >> path[i];
if(i == 0){
temp = findParent(path[i] - 1);
}
else{
if(temp != findParent(path[i] - 1)){
ans = false;
break;
}
}
}
if(ans){
cout << "YES\n";
}
else{
cout << "NO\n";
}
return 0;
}
int findParent(int num){
if(num == cities[num]){
return num;
}
else{
return num = findParent(cities[num]);
}
}
void Union(int a, int b){ // 그냥 도시의 정보만 입력하면 알아서 최고레벨의 부모를 찾아줌...
if(findParent(a) == findParent(b)){ // 중복확인
return;
}
cities[findParent(a)] = findParent(b);
}
// 두가지 기능에 집중하자...!
// 최고 레벨의 부모를 찾는 기능..
// 두 집합을 Union(합)하는 기능..
참고로 본인은 조건을 잘 못 읽어 상당히 오랫동안 헤매었다..ㅠㅠ
배열
을 이용해 자료들을 집합의 형태로 저장하면 어떤 부분에서는 관리에 용이하다.