[백준 / BOJ] C++ 3780 네트워크 연결

3780번: 네트워크 연결

 

문제

https://www.acmicpc.net/problem/3780

3780번: 네트워크 연결

 

 

풀이

정점들에 대해 I 쿼리는 두 정점을 연결하고 E 쿼리는 정점에 대해 루트 노드까지의 거리를 출력한다. 유니온 파인드 알고리즘을 사용해 해결했다. 보통의 유니온 파인드와 다른 점은 정점의 부모 노드를 루트 노드로 갱신하는 것이 아니라 각 정점 간 관계를 저장한다. 예를 들어 정점 i와 j를 이으면 p[i] = j 가 된다.

 

먼저 기본적인 큰 틀은 I 쿼리가 입력되면 정점에 대해 연결 관계를 기록하고 정점 간 거리를 기록한다. E 쿼리가 입력되면 시작 노드로부터 루트 노드까지 부모 노드를 통해 도달한 다음, 차례대로 돌아오며 거리를 누적해 간다. 돌아오는 매 순간 거리를 누적한 다음에는 부모 노드를 루트 노드로 바꾸어 재갱신하더라도 값이 바뀌지 않도록 한다. 루트 노드는 자기 자신까지의 거리를 가지고 항상 0이기 때문이다.

 

자세한 설명은 코드와 함께 주석으로 설명해놓았다.

 

 

코드

#include <bits/stdc++.h>
using namespace std;

vector<int> p, dist;

int find(int x) {
  if (p[x] != x) {
    // 루트 노드가 아니면 재귀 & 부모(루트) 노드 저장
    int node = find(p[x]);
    // 거리 누적
    dist[x] += dist[p[x]];
    // 부모 노드 갱신
    p[x] = node;
  }
  return p[x]; // 루트 노드면 자기 자신 return
}

void merge(int x, int y) {
  dist[x] = abs(x - y) % 1000; // 거리 저장
  p[x] = y; // 정점간 관계
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  int T;
  cin >> T;
  while (T--) {
    int N;
    cin >> N;
    // 부모 노드 배열 초기화
    p.resize(N + 1);
    iota(p.begin(), p.end(), 0);
    // 거리 배열 초기화
    dist.resize(N + 1);
    fill(dist.begin(), dist.end(), 0);
    while (1) {
      char c;
      cin >> c;
      if (c == 'E') { // E 쿼리
        int i;
        cin >> i;
        // 거리 갱신
        find(i);
        // i로부터 루트까지의 거리 출력
        cout << dist[i] << '\n';
      } else if (c == 'I') { // I 쿼리
        int i, j;
        cin >> i >> j;
        merge(i, j);
      } else { // O 쿼리(종료)
        break;
      }
    }
  }
  return 0;
}