_

1. 소개

결과, 문제, 데이터, 답안은 여기서 볼 수 있다.

2. Bronze

3. Silver

4. Gold

5. Platinum

5.1. Modern Art

문제

기본적으로 다른 색 위에 덧칠해진 색은 답에 포함될 수 없다는 점을 생각하면 된다. 각 색깔마다 최소 / 최대 x, y 좌표를 구하면 자신 위에 덧칠해진 색을 체크해줄 수 있다. 덧칠해진 색이 아닌 색의 수가 답인데, 예외로 전체에 칠해진 색이 한가지 뿐인 경우 \(N^2-1\)를 출력해준다.

5.2. Switch Grass

문제

다른 타입의 노드를 연결하는 에지들을 잘 관리해 줘서 쿼리마다 답을 빠르게 구해야 한다. 일단 답이 되는 에지는 무조건 Minimum Spanning Tree에 포함되어 있어야 하므로 그래프를 MST로 바꿀 수 있다. MST에서 DFS를 하면 각 에지가 부모 노드와 자식 노드를 잇는 에지로 바뀐다. 어떤 노드 v의 색이 바뀔 때, v를 부모 노드로 갖는 에지(여러 개)와 v를 자식 노드로 갖는 에지(1개)를 따로 처리한다.

Map을 통해 (노드 번호, 타입) 위치에 최소 길이 에지를 저장한 상태를 유지하면서 pq가 답을 top에 저장하고 있도록 잘 관리하여 답을 구할 수 있다.

5.3. COWBASIC

문제