[BOJ 14263] 카드 놓기

문제: https://www.acmicpc.net/problem/14263

 

풀이:

어떤 한 카드의 원래 영역을 생각 해 봅시다. 이 영역은 직사각형 모양이기 때문에, 주어진 종류의 모든 색을 포함하는 직사각형 영역을 포함해야 한다는 것을 알 수 있습니다. 여기서는 이런 직사각형 영역중 최소한의 영역만 생각하면 됩니다. 직사각형 영역이 더 크다는 것은 더 많은 (불필요한) 제약조건을 의미하고, 우리는 가능한 모든 상태에서 사전순 최소를 찾아야하기 때문입니다.

 

이제 각 직사각형 영역에 대해서, 해당 직사각형 영역에 다른 색이 올라와 있다는 것은, 덮이는 순서가 정해져있다는 것입니다. 해당 직사각형 영역 다음에 다른 색이 덮여야 합니다. 이를 이용하면 어떤 두 색 간의 덮는 순서를 알 수 있습니다. (해당 직사각형 영역에 빈 칸이 있는 경우를 주의합시다.)

 

이런 제약조건이 있을 때 사전순으로 가장 빠른 덮는 법을 찾는 것은 위상정렬으로 해결할 수 있습니다.

 

코드: https://www.acmicpc.net/source/share/c9bad872dd584a16b944f735e72db665