문제

동혁이는 친구들과 함께 여행을 가려고 한다. 한국에는 도시가 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를 출력한다.

예제

예제 입력
3
3
0 1 0
1 0 1
0 1 0
1 2 3

예제 출력
YES

접근

  • Disjoint-Set(Union-Find)를 공부하기 위해 찾은 문제다 보니 자연스럽게 이 방법으로 접근하게 되었다.

내가 생각한 풀이

  • 주어진 입력을 통해 union을 실행한 후 각각의 여행 루트(route)에 대해 root를 탐색하여 같은 root를 갖는다면 진행시키고 다른 root가 나올 경우 NO를 출력한다.

미처 생각하지 못했던것

  • 런타임 에러 때문에 2시간동안 헤맸다… 그런데 더 화나는건 그 이유를 못 찾았다는 거… 같은 입력에 대해서도 런타임 에러가 뜰 때도 있고 안 뜰 때도 있었다. 혹시 이런 문제를 겪어본 분이 계신다면 이유를 알려주세요..!

코드

#include<iostream>
#include<vector>
using namespace std;
int N,M,parent[201],rank_arr[201] = {0, };
bool map[201][201] = {0, };
vector<int> route;
int find(int n)
{
  if(n == parent[n]) return n;
  return parent[n] = find(parent[n]);
}
void merge(int u, int v)
{
  u = find(u); v = find(v);
  if(u == v) return;
  if(rank_arr[u] > rank_arr[v]) swap(u,v);
  parent[u] = v;
  if(rank_arr[u] == rank_arr[v]) ++rank[v];
}

int main(void)
{
  ios_base :: sync_with_stdio(false);
  cin.tie(NULL);

  cin>>N>>M;
  for(int i = 1 ; i<=N ; i++) parent[i] = i;
  for(int i = 1 ; i<=N ; i++)
  {
    for(int j = 1 ; j<=N ; j++)
    {
      cin>>map[i][j];
      if(map[i][j]) merge(i,j);
    }
  }
  for(int i = 0 ; i<M ; i++)
  {
    int t;
    cin>>t;
    route.push_back(t);
  }
  int initial_route = find(route[0]);
  for(int i = 1 ; i<route.size() ; i++)
  {
    if(initial_route != find(route[i])){
      cout<<"NO";
      return 0;
    }
  }
  cout<<"YES";
  return 0;
}