13344 Chess Tournament

Chess Tournament

www.acmicpc.net/problem/13344

 

1.접근

문제를 보고 동점인 경우에는 같은 차수의 집합이 생길거라고 생각해서 disjoint set을 바로 생각했다.

일관성이 있는지 없는지를 판단하려면 위상정렬을 시켜서 순서대로 진행했을때 위상정렬이 정상적으로 수행되면 일관성이 있는 것이고 차수가 0인게 존재하지않아서 큐에서 뽑을게없으면 사이클이 생겨 일관성이 없다고 판단했다.

 

2.풀이

중요한 것은 집합을 모두 만들고 > 연산을 수행하는 것이다. 처음에는 =,> 연산을 들어올때마다 했는데 바뀌는 것이 매번 많아서 코드가 복잡했다. 그래서 '='이 나왔을 때 유니온을 합치는 작업부터 모두 수행하고 그다음 '>' 작업을 했다.

모든 병합이 완료되면 경로 압축을 통해 부모노드를 정확히 해주고,union 배열의 부모노드 인덱스에 같은 부모를 가르키는 것들을 넣어서 집합을 만든다.또,하나의 배열(코드에서P)를 만들어 집합의 부모노드들 배열을 만들어 놓는다.

이제 '>'연산을 수행한다. a>b라는 입력이 들어온다면 a가 b를 이긴다는 뜻이다. 따라서 위상정렬 할 때 b가 a보다 먼저 나와야한다는 뜻 이므로 b간선에 a를 추가해주고 a의 차수를 1 높이면 된다.

하지만 이 문제에서는 집합이 있으므로 a의 부모노드를 찾고 b의 부모노드를 찾은 후 모두 부모노드의 연산으로 바꿀 것이다.a의 부모노드에 차수를 높이고 b의 부모노드의 간선에 추가해준다는 뜻이다.

 

빨강색이 각 집합의 부모노드라고 할 때 

각집합의 원소에서 화살표를 가는것이 아닌

부모노드의 집합에서 해야 놓치는 간선이 없다.

차수를 정해주려면 각 부모노드마다 간선이 어디서오는지 알아놓아야 한다(코드의 From_where)

그 배열의 길이가 차수일 것이다.

 

 

 

 

여기서 또 하나 생각해야 할 것은 중복되는 값들이 있을 수 잇다는 것이다. 예를 들어 (1,2)의 집합에서

1>3,2>3이 들어오면 (1,2)의 집합에는 3이 두개가 되서 차수가 부정확해질 수 있으므로 간선배열과 간선의 어디서오는지의 배열을  set자료형을 사용하여 중복을 없애주어야한다.

마지막에는 위상정렬로 순서를 돌려보며 위상정렬이 끝까지 되는지 안되는지 여부를 판단하면 된다.

부모노드의 차수가 0 일 때 그 집합의 모든 원소를 큐에 넣어서 n개 까지 카운트해주는 방법으로 확인했다.

안된다면 사이클이 생긴 것이다.

3.코드

4.배운점

• 저번에 실수했던 경로압축을 까먹지 않고 잘 썻다.
• 문제를 보자마자 union find와 위상정렬을 합쳐서 풀어야 된다는 것은 보였는데 =연산부터 다하고 > 연산을 실행해야 한다는 것을 알기 힘들었다
• 배열에 set자료형을 넣을 수 있다.
• enumerate를 사용하면 for 문을 쓸 때 몇번째인지와  원소를 편하게 알 수 있다.