[Python] 7538번 Incomplete chess boards (추후 보강 예정)

 

https://www.acmicpc.net/problem/7538

---

 

25/06/09

 

 

유명한 퍼즐 문제이다. 간단하게 구현만 하면 되는 문제로, 이걸 정당화하는데에는 조금 어려운 내용이 들어간다. 

---

 

문제 접근 방식:

 

 

주어진 요구 사항은, $8 \times 8$크기의 체스판이 주어지는데, 이 체스판의 두 곳에 구멍을 뚫어놓고, 남은 칸들을 $2 \times 1$크기의 도미노 타일로 전부 매울 수 있는지의 여부를 각 테스트 케이스마다 판단하는 것이다.

 

이 문제는 Mutilated chessboard problem이라는 이름으로 검색하면 위키에 잘 나와있다.

https://en.wikipedia.org/wiki/Mutilated_chessboard_problem

Mutilated chessboard problem - Wikipedia

먼저, 다음과 같은 사실을 알아야 한다.

 

도미노를 하나 덮으면 "무조건" 검은 칸 1개와 흰 칸 1개를 덮을 수 밖에 없다.

 

따라서, 우리가 만약 검은 칸 2개나 흰 칸 2개를 구멍 뚫어놨다면, 개수가 서로 맞지 않으므로 덮는 것이 불가능하다라는 사실을 잘 알 수 있다.

 

그렇다면, 검은 칸 1개와 흰 칸 1개를 없앤다면 어떻게 될까?

 

정답은 "항상 가능하다"인데, 이를 보여주는 가장 쉬운 방법으로 Gomory's Theorem이라고 불리우는, 수학자 Gomory가 제안한 해 구성적인 방법을 사용하여 증명한다.

도미노를 놓는 경로

다음 그림과 같이, 구멍이 없을 경우의 $8 \times 8$크기에서 가능한 경우를 헤밀토니안 경로로 이을 수 있다.

 

이후 흰 칸, 검은 칸이 하나씩 뚫린다면 뚫린 칸을 기준으로 경로가 분리될 것이다.

 

이후 분리된 두 경로를 따라가며 도미노를 놓으면 충분하다.

 

또 다른 방법으로는 이분 매칭의 개념과 홀의 결혼정리를 사용하여 보여주는 방법이 있다.

 

체스 판을 하나의 이분 그래프로 생각을 한다. 검은 정점은 검은 칸, 흰 정점은 흰 칸으로 생각한다.

 

그리고 간선은 칸과 인접한 다른 칸을 간선으로 생각한다.

 

도미노를 놓는 행위는 이러한 간선을 선택하는 행위이다. 즉, 매칭을 하는 것이다.

 

도미노를 전부 놓는 다는 뜻은, 모든 검은 칸이 모든 흰 칸에 대응되게끔 도미노를 놓을 수 있다는 뜻이고, 이는 곧 완전 매칭을 할 수 있다는 뜻과 같은 말이다.

 

흰 칸과 검은 칸이 각각 하나씩 뚫려있는 경우, 이를 홀의 결혼정리에 따라 항상 가능함을 보여줄 수 있다. (실제로 이를 사용하여 보여주는 과정을 엄밀하게 작성하려고 했으나, 생각보다 어려워서 이는 추후에 작성하기로 했다.)

 

홀의 결혼 정리는 완전 매칭에 관한 정리로 정리의 Statement는 다음과 같다.

 

Statement) 완전 매칭이 가능하다 $=$ 대응하는 정점 집합 $U$와 대응되는 정점 집합 $V$가 존재한다면, 대응하는 정점 집합 $U$의 임의의 부분 집합 $S$를 가져온다고 해도, 그 $S$와 이웃한 정점 집합 $N(S) \subset V$의 크기가 항상 $S$의 크기보다 크거나 같다.

 

직관적으로 생각해 봤을 때 흰 칸과 검은 칸이 하나씩 비어있으면, 어떤 하나의 칸을 잡으면 주변에 대응되는 칸이 무조건 1칸 이상 존재하므로 이 Statement가 성립함을 확인할 수 있다.

 

엄밀하게 서술하지는 못하나, 일단 이 정도로만 서술할 수 있을 것 같다.

 

만약 같은 색깔의 칸을 고른다면 위의 Statement가 불가능한데, 예를 들어 모서리와 이웃한 두 칸이 비어있다고 해보자.

 

이 두 칸은 같은 색깔이고, 모서리를 고른다면, 모서리 칸 주변에 대응되는 칸이 없으므로, 주변에 대응되는 칸이 무조건 1칸 이상 존재한다고 이야기할 수 없다.

---

아래는 내가 위의 접근 방식과 같이 작성한 파이썬 코드이다. 더보기를 누르면 확인할 수 있다.

# 7538번 Incomplete chess boards
# 애드혹
import sys
input = sys.stdin.readline

N = int(input())
for i in range(1, N+1):
    x1, y1, x2, y2 = map(int, input().split())
    print(f'Scenario #{i}:')
    dx, dy = abs(x1-x2), abs(y1-y2)
    if (dx % 2) != (dy % 2):
        print(1)
    else:
        print(0)
    print()