[백준]3830 교수님은 기다리지 않는다

K_Gs·2022년 4월 12일
0

BOJ

목록 보기
7/13
post-thumbnail

[정답이 아니라 풀이 기록입니다.]

교수님은 기다리지 않는다

여러 쿼리가 들어온다.
! a b c : b가 a보다 c만큼 무겁다는 것을 기록
? a b : b가 a보다 얼마나 무거운지 출력

접근

  1. 무게는 상대적으로 기록됩니다.
  2. 무게 비교가 불가능 할 수도 있습니다.

구현

비교 가능 여부

임의의 원소 a,b가 있을때 a,b가 비교가능하기위해선 ! a b (임의의 값) 쿼리가 1번은 들어와야합니다.

그리고 또다른 원소 c가 있을때 a와 c를 비교하기 위해선 직접적으로 ! a c (값) 쿼리가 들어오거나 ! b c (값) 쿼리를 통해 상대적으로 연결되어야합니다.

이렇게 중간 과정을 거치거나, 혹은 직접적으로 연결되어있는지 판단하는 것은 유니온 파인드로 할 수 있습니다.

비교를 하는 쿼리인 ? a b 가 들어왔을때 find(a)와 find(b)의 값이 다르다면 둘은 다른 집합이고 비교를 할 수 없기에 UNKNOWN을 출력합니다.
둘의 값이 같다면 비교를 해서 출력하면 됩니다.

비교의 기록

유니온 파인드는 parent배열을 통해 부모원소를 가리키는 방식으로 저장됩니다.
이때 집합내에서 얼마나 무겁고 가벼운지에 대한 관계도 알아야하기에 value배열을 만들어 부모원소와 자신간의 상대적 무게도 기록합니다.

b가 a보다 c만큼 무겁다는 쿼리가 들어오면 b의 부모로 a를 넣고, b가 부모보다 c만큼 무겁다고 value[b]에 기록하거나, a의 부모로 b를 넣고, b가 부모보다 c만큼 가볍다고 value[a] 기록하면 됩니다.

문제상에 b가 a보다 무겁다는 식으로 들어오기에 저는 전자로 기록하겠습니다.

집합 내부 비교

집합 내부의 두 원소 a,b가 있을 때 비교를 해봅시다.
a와 b를 비교하기 위해선 기준이 되는 어떤 것이 필요합니다.
그 기준을 c라 하였을때, a가 c보다 A만큼 무겁고 b가 c보다 B만큼 무겁다면 둘의 무게 차이는 abs(A-B)가 되는 거죠
기준을 찾아봅시다.
모든 원소들은 자신의 부모와 상대적인 무게 차로 기록되어있습니다.
즉, 집합내의 어떤 원소든 따라 올라가다보면 집합의 대표원소를 만나고, 그 대표원소와의 상대무게를 구할 수 있습니다.
그렇기에 find를 했을 때 나오는 결과인 대표원소를 기준점으로 삼으면 됩니다.
find를 구현하면서 기준점과 상대무게를 구해봅시다.

기준점과의 상대무게(find 구현)

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

대표원소를 찾고 그 원소의 번호를 반환하는 find의 기본 구현입니다.
여기다 대표원소와의 상대무게를 얻어야하기에 부모원소와 대표원소간의 상대무게를 바탕으로 구해보겠습니다.

int find(int x){
	if(parent[x] == x){
    	value[x] = 0;
        return x;    
    }
    int y = find(parent[x]);
    value[x] += value[parent[x]]
    return y;
}

자신과 부모원소 사이의 상대무게 + 부모원소와 대표원소 사이의 상대무게
= 자신과 대표원소 사이의 상대무게

이제 find(a)를 호출하면 value[a]에 대표원소와의 상대무게가 저장됩니다!
두 원소간의 무게 차이를 구하기전에 find를 호출해주면 되는데, 위에서 비교가능여부를 확인하기 위해 find를 한번 호출하기에 추가로 호출해줄 필요는 없습니다.

경로 압축 최적화(find 최적화)

find의 주기능은 대표원소를 찾아서 리턴하는 것이고 value를 구하는 것은 부가적인 기능입니다.
그래서 대표원소를 찾을때마다 부모원소를 통해 계속 올라가게 되고 그때마다 value가 이상한 값으로 갱신되게 됩니다.

위 코드에서 부모가 쓰이는 것은 value값을 구할때 단 한번입니다.
즉, value값을 구하게되면 부모원소와의 연결은 필요가 없고 대표원소를 찾기위해 대표원소와의 연결만 필요하게 됩니다.

그렇기에 부모를 대표원소로 바꿔줍니다.
또 find(a)를 하게되면 a뿐만 아니라 대표원소와 a사이에 연결된 원소들의 value도 구해지기에, 사이 원소들도 전부 부모를 대표원소로 바꿔줍니다.

int find(int x){
	if(parent[x] == x){
    	value[x] = 0;
        return x;    
    }
    int y = find(parent[x]);
    value[x] += value[parent[x]]
    parent[x] = y;//부모를 대표원소로
    return y;
}

집합 합치기(merge 구현)

merge는 항상 대표원소끼리 이루어집니다.
그리고 쿼리는 ! a b c의 형식으로 들어옵니다.
a와 b가 대표원소가 아닐 수 있기에 find를 통해 대표원소를 찾아줍니다.

int x = find(a);
int y = find(b);

그리고 저는 부모원소가 자식원소보다 가볍다로 문제를 풀었기에 merge도 무거운쪽 대표원소가 자식으로 들어가야합니다.

a의 대표원소는 a보다 A만큼 가볍고, b의 대표원소는 b보다 B만큼 가볍다 가정하겠습니다.
a b c의 형식으로 쿼리가 들어왔기에 b가 a보다 c만큼 무겁습니다.
그렇기에 a의 대표원소는 a보다 A만큼 가볍고, b의 대표원소는 a 보다 B-c만큼 가볍습니다.

즉, A가 B-c보다 크다면 a의 대표원소가 더 가벼운 원소이기에 a의 대표원소가 부모원소가 되고,
반대라면 b의 대표원소가 더 가벼운 원소이기에 b의 대표원소가 부모원소가 됩니다.

void merge(int a,int b,int c){
  int x = find(a);
  int y = find(b);
  int temp = value[a]-(value[b]-c);
  if (temp>=0) {
		parent[y] = x;
		value[y] = abs(temp);
  }
  else {
		parent[x] = y;
		value[x] = abs(temp);
  }	
}

abs(A-(B-c))가 대표원소간의 상대무게이기에 자식으로 들어가는 대표노드의 value에 저장해줍니다.

답 출력

? a b 쿼리가 들어올때 b가 a보다 얼마나 무거운지 출력해야합니다.
위에서 이야기했듯 find(a) != find(b)라면 답을 구할 수 없기에 UNKNOWN을 출력합니다.

if (find(a) != find(b)) {
		printf("UNKNOWN\n");
}

그리고 find(a) == find(b)라면 value에 대표원소와의 상대무게가 저장되어있기에 value[b]-value[a]를 출력합니다.

if (find(a) != find(b)) {
		printf("UNKNOWN\n");
}
else {
		printf("%lld\n",value[b]-value[a]);
}

이것을 테스트 케이스마다 반복하면 됩니다.
그리고 테스트케이스 시작시 아무것도 하기전에 집합의 대표는 자기 자신이기에 1~n까지 전부 parent[i] = i, value[i] = 0으로 초기화 해줍니다.

for (int i = 1; i <= n; i++) {
		value[i] = 0;
		parent[i] = i;
}

마무리

유니온 파인드를 떠올리고 가중치를 관리하는 부분이 어려웠습니다.

profile
~(~o~)~

0개의 댓글