추석맞이 POI 풀이 : Rooks

문제 링크: https://www.acmicpc.net/problem/8103

문제 요약

n x n 크기의 체스판 위에 n개의 룩을 서로가 서로를 잡을 수 없게 배치할 것이다. 이 때, i번째 룩은 (ai,bi) 에서 (ci,di)위치 사이에만 놓을 수 있다. 모두 배치할 수 있다면 그렇게 배치할 수 있는 경우를 아무 것이나 출력하고, 배치할 수 없다면 NIE를 출력하라.

풀이

록끼리 서로가 서로를 잡을 수 없게 배치하려면, 하나의 룩이 배치된 위치와 같은 행 또는 열에는 다른 룩이 배치되어선 안 된다. 또, 룩은 항상 일직선으로만 위치를 차지하기 때문에 행과 열은 독립적이다. 따라서, 행과 열을 분리해서 보아도 상관없다. 룩이 x좌표에서 어느 위치에 있느냐는 그 룩의 y 좌표에서의 배치에는 전혀 영향을 끼치지 않기 때문이다.

그러면 x와 y좌표를 서로 분리해서 생각해보자. 하나의 좌표만 고려했을 때 이 문제는 길이 n의 배열에서 n개의 구간이 주어졌을 때, n개의 모든 칸을 n개의 구간에 각각 하나씩 배분해줄 수 있는지를 묻는 문제로 바뀐다. n 범위가 3000밖에 안 되기 때문에 이런 구간을 커버할 수 있는 방법은 굉장히 다양하다. 복잡하게는 이분매칭 같은 걸 써도 충분히 통과가 될 것이다.

내가 접근한 방법은 그리디한 방법이었다. 어떤 칸 p에 대해서, 아직 사용하지 않은 구간 중에서 p를 포함하는 구간 집합을 S라고 하자. 이 집합 S에 혹한 구간 중에서 오른쪽 끝 구간 r이 가장 p에 가까운 것을 선택하는게 항상 최적임은 어렵지 않게 증명할 수 있다. 따라서, 모든 칸 p에 대해서 그 칸을 포함하며 거기에 가장 가까운 지점이 무엇인지를 유지하며 답을 골라나가면 O(nlogn)에 답을 구할 수 있다.