[백준] 1976번 여행 가자 C++ 코드

유니온 파인드 코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
using namespace std;

int n,m,a,b,c,lst[203],road[1003],temp;
bool ok = true;
set<int> st;
int find(int x) {
  if(x == lst[x]) return x;
  return lst[x] = find(lst[x]);
}

void merge(int x, int y) {
  x = find(x);
  y = find(y);
  if(x > y) lst[x] = y;
  else lst[y] = x;
}

int main() {
  cin >> n;
  cin >> m;
  for(int i = 1; i < n + 1; i++) lst[i] = i;
  for(int i = 1; i < n + 1; i++) {
    for(int j = 1; j < n + 1; j++) {
      cin >> temp;
      if(temp == 1) {
        merge(i,j);
      }
    }
  }
  for(int i = 0; i < m; i++) {
    cin >> temp;
    st.insert(find(temp));
  }
  if(st.size() > 1) ok = false; // 1개로 연결된 것이 아니면
  cout << (ok ? "YES" : "NO" ) << '\n';
  return 0;
}

 

DFS 코드

#include <iostream>
#include <vector>

using namespace std;

int n,m, visited[203], temp;
bool ok = true;

vector<int> adj[203];
vector<int> v;

void dfs(int x) {
  visited[x] = 1;
  for(int i : adj[x]) {
    if(!visited[i]) dfs(i);
  }
}

int main() {
  cin >> n;
  cin >> m;
  for(int i = 1; i < n + 1; i++) {
    for(int j = 1; j < n + 1; j++) {
      cin >> temp;
      if(temp == 1) {
        adj[i].push_back(j);
      }
    }
  }

  for(int i = 0; i < m; i++) {
    cin >> temp;
    v.push_back(temp);
  }
  dfs(v[0]);
  for(int i = 0; i < m; i++) {
    if(!visited[v[i]]) {
      ok = false;
      break;
    }
  }
  cout << (ok ? "YES" : "NO") << '\n';
  return 0;
}

 

dfs와 유니온 파인드 두 가지 방법으로 해결할 수 있었다. 우선 문제 조건에 따라 모든 노드가 연결되어 있어야 한다. union-find의 경우, 입력에서 주어지는 값들을 모두 연결하고 find를 이용해 부모 노드의 개수를 센다. 2개 이상이면 여행을 할 수 없다.

 

DFS의 경우에는, 주어지는 임의의 한 점에서 dfs를 실행한 후, 방문하지 않은 구간이 있으면 false, 있으면 true로 구분하면 된다.