대회는 끝났지만 다시 풀어보면서 풀이를 올려보려고 한다.
K. Tiling Polyomino
어제 문제가 올라왔지만 [계ㅡ측] 당해서 오늘 부관참시를 했다.
풀이는 굉장히 다양하게 존재하는 것 같으나 내 풀이(4500B)와 아인타 선생님의 훌륭한 풀이(1800B)를 적겠다.
[4500B 망한 풀이] 모든 점의 deg가 2이므로 대부분의 경우 그래프가 뭉쳐있게 생겼다. 만약 deg가 2인 P의 점들이 모두
[관찰 1]이런 모양이라면, 단방향의 타일만 가지고도 덮을 수 있음이 쉽게 보장된다.
[관찰 2]따라서 정사각형이 line을 이루게 될 경우만 따로 고려해주면 되고, 우리는 큰 컴포넌드들을 하나로 묶고, (deg가 2인) line의 점들로 이루어진 트리를 만들 수 있다.
트리의 리프는 무조건 큰 컴포넌트임이 보장되므로 리프에서부터 하나씩 제거해 나가면 된다. 하지만 이럴 경우 코딩이 굉장히 복잡해지는데, 다음과 같은 경우 때문이다.
현재 deg가 2이면서 component를 연결하는 점들을 빨간색으로 표시해놨다. 현재 남은 모든 칠해지지 않은 컴포넌트들이 리프이므로 제일 왼쪽의 리프를 제거했다고 해보자. 그러면 파란색 점(전에 빨간색이 아니었던 점)이, 새로운 그래프에서는 빨간색 점이 됨을 알 수 있다.
실제 대회 때에는 리프를 떼어낼 때마다 파란색 점이 빨간색으로 바뀌게 되는지를 확인해가는 코드를 짰고, 안그래도 복잡한 코드가 더 터지게 하는데 큰 공을 세웠다.
하지만 여기서 생각을 조금 더 해보면, 우리는 저 파란색 점을 리프를 떼어내지 않고도 알 수 있다는 점을 깨달을 수 있다...
[관찰3] 한 점을 포함하는 네개의 $2\times2$ 정사각형이 모두 P에 포함되어있지 않으면 빨간색으로 칠해주면 된다.
이렇게 칠해주면, 리프를 제거해주는 것이 조금 더 수월하다.
[1800B 훌륭한 풀이] 이것을 의도하고 낸 문제인지는 모르겠으나, [4500B 망한 풀이]보다 더 깊은 관찰을 요구한다.
[관찰] 다음과 같이 deg가 2인 점들 중에서도 양 옆이나 위 아래로만 연결된 점들을 특별한 점이라고 하자. 앞의 관찰에 따르면 이 점들은 그래프를 두개로 완전히 갈라놓는다.
관찰에 유의하며 dfs를 돌자. dfs를 돌 때 자신의 부모중에서 가장 가까운 특별한 점의 방향(양 옆 or 위 아래)를 저장하자. 모든 점은 저장된 방향의 도미노로 채울 수 있다. 정말 훌륭한 관찰이다...