10589번 마법의 체스판

문제 설명

이번 문제는 크기가 n * m인 마법의 체스판에서 직사각형을 선택해서 검은색은 흰색으로 흰색은 검은색을 바꿀 수 있을 때, 모든 칸의 색상을 같게 만들 수 있는 직사각형의 좌표를 출력하는 문제입니다.

 

문제 풀이

아이디어

체스판의 길이가 짝수일 때와 홀수일 때의 규칙을 찾아보겠습니다.

체스판 경우의 수

모든 칸을 채울 색 정하기

우선 짝수이든 홀수이든, 가장 왼쪽의 가장 윗칸의 색이 다른 색보다 많거나 같다는 것을 알 수 있습니다.

그러므로, 모든 칸을 가장 왼쪽 윗 칸의 색(이하 A색으로 부르겠습니다.)으로 바꾸도록 하겠습니다.

 

대칭 이루기

경우 2번 홀수 * 홀수 인 체스판을 보도록 하겠습니다.

홀수 * 홀수인 체스판은 좌우상하로 대칭을 이루고 있습니다. 이럴 경우, 모든 색을 A로 바꾸는 회수를 살펴보도록 하겠습니다.

 

가장 왼쪽, 윗 칸을 1,1(행,열)이라고 할 경우

아래 사진은 차례대로 (1,2,5,4) , (1,4,5,4) , (2,1,2,5) , (4,1,4,5) 를 바꾼 경우입니다.

대칭을 이뤘을 경우

위와 같이 대칭을 이뤘을 경우, A색이 아닌 가장자리의 반대편 가장자리까지 포함한 긴 직사각형 부분의 색을 바꿔주면 전체가 A색이 되도록 바꿀 수 있습니다.

위 아이디어를 통해, 우선 대칭을 만들고 A색이 아닌 가장자리의 반대편 가장자리까지 포함한 긴 직사각형 부분의 색을 바꿔주는 방식으로 진행해보도록 하겠습니다.

 

꼭지점 채우기

길이가 짝수인 체스판의 경우 꼭짓점이 A색이 아닌 칸이 존재합니다. 그러므로, 이 꼭지점을 A색으로 바꾸기 위한 시도가 한 번 필요합니다.

 

이 때, 꼭지점을 채울 때 필요한 직사각형을 최대한 크게 하여 다른 칸의 색을 변경하는 회수를 최소로 해야합니다.

 

경우 1. 짝수 * 짝수인 경우

오른쪽 위 칸이 A색이 아니고 대칭을 만들어주기 위해서는 (1,3,2,4) 직사각형을 바꿔주면 됩니다.

왼쪽 아래 칸이 A색이 아니므로 대칭을 만들어주기 위해서는 (3,1,4,2) 직사각형을 바꿔주면 됩니다.

짝수 * 짝수

-> 대칭을 만들면서 꼭지점을 A색으로 만들기 위해, 체스판을 4군데로 나눌 경우 오른쪽 위와, 왼쪽 아래쪽을 색을 바꿔주면 됩니다.

 

경우 2. 짝수 * 홀수

짝수가 있는 행이나 열의 마지막 줄에 포함된 꼭지점에 색이 A가 아닌 꼭지점이 존재하므로 (3,1,4,5) 직사각형의 색을 바꿔주면 됩니다.

짝수 * 홀수

-> 대칭을 만들면서 꼭지점을 A색으로 만들기 위해, 체스판을 짝수가 있는 행이나 열을 반절로 나눌 경우 꼭지점의 색이 A가 아닌 부분의 직사각형의 색을 바꿔주면 됩니다.

짝수 * 홀수, 홀수 * 짝수 인 경우 똑같은 규칙을 적용해주면 됩니다.

 

풀이

입력 받은 체스판의 행과 열의 짝수 여부에 따라, 위의 규칙대로 진행하면 됩니다.

1. 꼭지점을 A색으로 바꿔줍니다. A색을 바꿀 때, 상하 좌우 대칭을 이룰 수 있게 해주는 최대의 직사각형의 색을 바꿔줍니다.
2. 대칭이 된 체스판에서, A색이 아닌 가장자리의 반대편 가장자리까지 포함한 긴 직사각형 부분의 색을 바꿔줍니다.

예외 경우

행이나 열이 짝수인 경우를 대칭으로 만든 이후 상황을 보겠습니다.(8*8 체스판)

8 * 8 대칭을 이룬 체스판

2,4,5,7 행과 2,4,5,7 열의 색을 바꿔주면 되는데, 이 때 4,5는 하나의 직사각형으로 색을 바꿔줄 수 있으므로, 짝수와 같은 경우 중앙에 위치한 직사각형 두 개는 하나의 직사각형으로 묶어주어야 합니다.

 

 

 

해결

이번 문제는 체스판의 색을 바꾸는 규칙을 찾는 것이 오래 걸렸던 문제였습니다. 꼭지점을 먼저 바꾼다는 생각을 한 뒤에 규칙을 찾을 수 있었습니다.

 

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

10589번: 마법의 체스판

코드 링크 : https://github.com/beomseok37/baekjoon/blob/master/new!/10589.py