[BOJ] 1976 번 - 여행 가자

백준 1976번 - 여행 가자

시간제한	메모리 제한	제출	정답	맞은 사람	정답 비율
2 초	128 MB	10471	3988	3008	39.009%

문제

동혁이는 친구들과 함께 여행을 가려고 한다. 한국에는 도시가 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라는 여행경로를 통해 목적을 달성할 수 있다.

도시들의 개수와 도시들 간의 연결 여부가 주어져 있고, 동혁이의 여행 계획에 속한 도시들이 순서대로 주어졌을 때(중복 가능) 가능한지 여부를 판별하는 프로그램을 작성하시오.

입력

첫 줄에 도시의 수 N이 주어진다. N은 200이하이다. 둘째 줄에 여행 계획에 속한 도시들의 수 M이 주어진다. M은 1000이하이다. 다음 N * N 행렬을 통해 임의의 두 도시가 연결되었는지에 관한 정보가 주어진다. 1이면 연결된 것이고 0이면 연결이 되지 않은 것이다. A와 B가 연결되었으면 B와 A도 연결되어 있다. 마지막 줄에는 여행 계획이 주어진다.

출력

첫 줄에 가능하면 YES 불가능하면 NO를 출력한다.

---

예제 입력 1

3
3
0 1 0
1 0 1
0 1 0
1 2 3

예제 출력 1

YES

 

 

출처

www.acmicpc.net/problem/1976

1976번: 여행 가자

알고리즘 분류

• 그래프 이론
• 자료 구조
• 그래프 탐색
• 분리 집합

접근 방법

첫번 째 풀이 

처음 문제를 봤을 때는 플로이드 와샬 알고리즘으로 모든 정점 간의 최단 거리를 구하고 ( 연결 되지 못한 경우에는 INF 로 )

주어진 여행 경로를 따라 연결 되어있는 지 여부만 확인 하면 된다고 생각했다.

 

예를 들어 여행계획이 E - C - B - C - D 라고 하자

그러면 E-C의 최단거리를 구해서 그 값이 INF 미만일 경우  E에서 C로 가는 경로가 존재한다. 이후 C-B까지의 최단거리가 INF 미만인 경우 C에서 B로 가는 경로가 존재한다. (이하 생략) 

다음과 같은 방식으로 생각하였고 실제 N도 200이하여서 무난하게 AC를 받았다.

 

단, 여기서 주의해야 할 점은 C-C 같이 여행경로는 중복이 가능하다는 것이다.

이 부분만 유의하여 자기 자신에게 오는 경로가 있는 것으로 처리를 해주면 된다.

 

소스 코드1 ( Floyd Warshall )

#include <bits/stdc++.h>
using namespace std;
int N, M;
int board[201][201];
int dist[201][201] ;
int main(void){
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    cin >> N >> M;
    // 1. 모든 쌍들의 최단 거리를 계산
    // 이것들의 합이 INF 이상이 되면 해당 경로는 없는 것이다.

    for(int i=1; i<=N; i++){
        for(int j=1; j<=N; j++)
            cin >> board[i][j];
    }

    vector<int> travelPlan(M);
    for(int i=0; i<M; i++){
        cin >> travelPlan[i];
    }


    for(int i=1; i<=N; i++){
        for(int j=1; j<=N; j++){
            dist[i][j] = board[i][j] > 0 ? 1 : 1e9;
            if( i == j )
                dist[i][j] = 1;
        }
    }


    // dist 계산 ( 플로이드 와샬 )
    for(int k=1; k<=N; k++){
        for(int i=1; i<=N; i++){
            for(int j=1; j<=N; j++){
                if( dist[i][j] > dist[i][k] + dist[k][j] )
                    dist[i][j] = dist[i][k] + dist[k][j];
            }
        }
    }

    bool canTravel = true;
    for(int i=0; i<M-1; i++){
        if( dist[travelPlan[i]][travelPlan[i+1]] >= 1e9 ){
            canTravel = false;
            break;
        }
    }

    if( canTravel ) cout << "YES";
    else cout << "NO";


    return 0;
}

 

두번 째 풀이

첫번 째 풀이로 문제를 풀 고 난 후, 해당 문제의 알고리즘 분류가 Disjoint Set이라는 것을 알게 되었다.

Disjoint Set은 서로 다른 특정 원소가 어느 집합에 포함되어 있는 지 빠른 시간 내에 확인 하고 싶을 때 유용하다.

이 문제에서 집합을 연결되어 있는 노드들 이라고 가정하자.

이렇게 잡아도 문제가 없는 이유는 A-B가 연결되고 B-C가 연결되었을 때  A-C도 경로가 존재하기 때문이다.( A-B-C 가 하나의 서로소 집합)

 

그러면 간단하게 여행 경로상에 있는 모든 노드들이 같은 Disjoint Set에 존재하는 지에 대한 사실만 따져주면 된다.

 

자 그러면, 어떻게 Union 연산을 처리해 줄까?

해답은 그래프 탐색이다. BFS나 DFS알고리즘으로 모든 그래프를 순회하며 같은 방문하는 새로운 노드들을 이때 까지 방문한 Disjoint Set에 포함 시켜 준다. 

그러면 모든 노드들에 대해서 그래프 탐색을 진행하고 나면 결론적으로 다른 경로 상에 존재하는 노드들 끼리 서로소 집합으로 분리가 된다.

 

한번 방문 했던 노드는 특정 Disjoint Set에 포함되는 것이 자명하므로, 방문 하지 않는 노드 위주로 DFS를 돌렸다.

 

소스 코드2 ( Disjoint Set )

#include <bits/stdc++.h>
using namespace std;
int N, M;
bool board[201][201]; // 단순 연결 상태 확인
bool visited[201] = {false, }; // 그래프 탐색을 위함

int parent[201] ; // i번째 노드의 부모를 나타낸다.
int rnk[201];
int find(int u){
    if( u == parent[u] )
        return u;
    // path compression
    return parent[u] = find(parent[u]);
}
void _union(int u, int v){
    u = find(u), v = find(v);

    if( u == v ) return;
    if( rnk[u] > rnk[v] )
        swap(u,v);

    // rnk[u] <= rnk[v] 가 보장
    parent[u] = v;
    if( rnk[u] == rnk[v] )
        rnk[v] += 1;

}
void DFS(int start){
    if( start > N )
        return;

    for(int i=1; i<=N; i++){
        if( board[start][i] == true && !visited[i] ){
            visited[i] = true;
            // 분리 집합에 추가 시킨다.
            _union(start, i);
            DFS(i);
        }
    }
}
int main(void){
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    cin >> N >> M ;

    for(int i=1; i<=N; i++){
        for(int j=1; j<=N; j++)
            cin >> board[i][j];
    }

    vector<int> travelPlan(M);
    for(int i=0; i<M; i++)
        cin >> travelPlan[i];


    // disjoint set 초기화
    for(int i=1; i<=N; i++) {
        parent[i] = i;
        rnk[i] = 1;
    }

    // 모든 노드를 그래프 탐색 한다.
    for(int i=1; i<=N; i++){
        DFS(i);
    }

    bool canTravel = true;
    for(int i=0; i<M-1; i++){
        int d1 = travelPlan[i], d2 = travelPlan[i+1];
        if( find(d1) != find(d2) ){
            canTravel = false;
            break;
        }
    }

    if( canTravel ) cout << "YES\n";
    else cout << "NO\n";

    return 0;
}