[백준] 1976. 여행가자

[문제]

www.acmicpc.net/problem/1976

1976번: 여행 가자

[풀이]

도시간의 연결 정보가 주어지고, 여행 경로가 주어진다.

도시가 연결되어 있으면 이동할 수 있고 연결되어 있지 않다면 이동할 수 없다. 

여행경로를 통해 여행을 할 수 있는지 구하는 문제이다.

 

이 문제는 유니온 파인드(Union-Find)를 통해 풀었다.

 

먼저 parent 배열을 자기 자신으로 초기화 해준다.

연결정보를 입력으로 받으면 두 개의 node에 대해 parent를 같게 해주어 하나의 집합에 속하도록 한다.

 

여행 경로를 가지고 각 노드에 대해 루트 노드를 확인하여 이동할 수 있는지를 판단한다.

루트 노드가 다르다면 서로 다른 집합에 속하는 것이므로 이동할 수 없다.

따라서 'NO'를 출력하고 끝내면 되고

모든 노드에 대해 루트 노드가 같다면 하나의 집합에 속하는 것이므로 이동할 수 있다.

 

[코드]

시간 : 4ms

#include <iostream>
#include <vector>

#define MAX 200

using namespace std;

int map[MAX][MAX]={0,};
int parent[MAX];

vector <int> _path;

int N,M;

int find(int idx)
{
    if(idx == parent[idx])  return idx;
    else{
        parent[idx] = find(parent[idx]);
        return parent[idx];
    }
}

void unit(int idx1 ,int idx2)
{
    idx1 = find(idx1);
    idx2 = find(idx2);
    
    if(idx1 != idx2)
    {
        parent[idx2] = idx1;
    }
}
int main(void)
{
    scanf("%d %d", &N,&M);
    
    for(int i=0;i<N;i++){
        parent[i] = i;
        for(int j=0;j<N;j++)    scanf("%d",&map[i][j]);
    }
    
    for(int i=0;i<N;i++){
        for(int j=0;j<N;j++){
            if(map[i][j] == 1)  unit(i,j);
        }
    }
    
    for(int i=0;i<M;i++){
        int v;
        scanf("%d",&v);
        _path.push_back(v-1);
    }
    
    for(int i=0;i<M-1;i++){
        if(find(_path[i]) != find(_path[i+1])){
            printf("NO");
            return 0;
        }
    }
    
    printf("YES");
    return 0;
}