Baymax

열심히 화이팅

2 분 소요

문제

상근이는 매일 아침 실험실로 출근해서 샘플의 무게를 재는 일을 하고 있다. 상근이는 두 샘플을 고른 뒤, 저울을 이용해서 무게의 차이를 측정한다.

교수님의 마음에 들기 위해서 매일 아침부터 무게를 재고 있지만, 가끔 교수님이 실험실에 들어와서 상근이에게 어떤 두 샘플의 무게의 차이를 물어보기도 한다. 이때, 상근이는 지금까지 잰 결과를 바탕으로 대답을 할 수도 있고, 못 할 수도 있다.

상근이는 결과를 출근한 첫 날부터 공책에 적어 두었다. 하지만, 엄청난 양의 무게가 적혀있기 때문에, 교수님의 질문에 재빨리 대답할 수 없었다. 이런 상근이를 위해서 프로그램을 만들어 주자.

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다.

각 테스트 케이스의 첫째 줄에는 샘플의 개수 N (2 ≤ N ≤ 100,000)과 상근이가 실험실에서 한 일의 수 M (1 ≤ M ≤ 100,000)이 주어진다.

다음 M개 줄에는 상근이가 실험실에서 한 일이 주어진다. 상근이가 무게를 쟀다면 ! a b w와 같은 형식으로 주어진다. 이는 b번 샘플이 a번 샘플보다 w그램 무겁다는 뜻이다. (a ≠ b, 1 ≤ a,b ≤ N, -1,000,000 ≤ w ≤ 1,000,000)

상근이가 어떤 두 샘플의 무게의 차이를 알아보고 싶다면, ? a b와 같은 형식으로 주어진다. 이는 b번 샘플이 a번 샘플보다 얼마나 무거운지를 알아보고 싶다는 뜻이다. (a ≠ b, 1 ≤ a,b ≤ N)

마지막 줄에는 0이 두 개 주어진다.

예제 입력 1

2 1
! 1 2 1
4 5
! 1 2 1
! 3 4 2
! 1 3 3
? 2 4
? 1 4
0 0

출력

교수님의 질문 (? a b)이 입력으로 들어올 때마다, 지금까지 측정한 결과를 이용해서 대답할 수 있다면, b번 샘플이 a번 샘플보다 얼마나 무거운지 출력한다. 불가능한 경우에는 “UNKNOWN”을 출력한다.

예제 출력 1

1
-1
UNKNOWN
100
200
-50

풀이

문제 해결 방법

이 문제는 서로소 집합(Disjoint Set)을 응용하여 해결할 수 있습니다. 주요 해결 단계는 다음과 같습니다:

  1. 분리 집합 구현: 각 샘플을 노드로 하는 분리 집합을 구현합니다.
  2. 무게 차이 저장: 각 샘플과 부모 노드와의 무게 차이를 저장합니다.
  3. 경로 압축: Find 연산 시 경로 압축을 하면서 무게 차이도 갱신합니다.
  4. Union 연산: 두 집합을 합칠 때 무게 차이를 고려하여 합칩니다.

이 알고리즘의 시간 복잡도는 O(M × α(N))입니다. 여기서 α(N)은 애커만 함수의 역함수입니다.

코드

#include<stdio.h>
#include<algorithm>

using namespace std;

int n, m;
int uni[100001];
int dist[100001];

int getParent(int x)
{
    if (uni[x] == x) return x;

    int pa = getParent(uni[x]);
    // uni[x] 업데이트 하기 전에, dist먼저 업데이트
    dist[x] += dist[uni[x]];
    return uni[x] = pa;
}

int main()
{
    int i, j;
    for (;;)
    {
        scanf("%d%d", &n, &m);
        if (n == 0 && m == 0)
            break;

        for (i = 1; i <= n; i++)
        {
            uni[i] = i;
            dist[i] = 0;
        }

        char c;
        for (i = 1; i <= m; i++)
        {
            scanf(" %c", &c);
            int a, b, w;
            if (c == '!')
            {
                scanf("%d%d%d", &a, &b, &w);

                int pa = getParent(a);
                int pb = getParent(b);
                uni[pb] = pa;
                dist[pb] = w - dist[b] + dist[a];
            }
            else
            {
                scanf("%d%d", &a, &b);

                int pa = getParent(a);
                int pb = getParent(b);

                if (pa == pb)
                    printf("%d\n", dist[b] - dist[a]);
                else
                    printf("UNKNOWN\n");
            }
        }
    }
    return 0;
}

댓글남기기

참고