[BOJ:1018] 체스판 다시 칠하기

Link : https://www.acmicpc.net/problem/1018\](https://www.acmicpc.net/problem/1018)

Note

문제에서 주어진 규칙을 어떻게 알고리즘으로 구현할 것인지 생각하면 된다. 직관적으로 생각해보기 위해서 4\*4일 때를 기준으로 먼저 생각해보고 크기를 생각해보았다. 여기서 좀 더 빠르게 구할 수 있는 규칙을 발견했다. 0행 0열이 W일 때와 B일 때로 나누어서 생각하지말고, W이든 B이든 0행 0열의 값을 기준으로 나머지 칸들이 문제에 주어진 규칙에 맞는지 모두 확인하고 다시 칠해야할 칸들의 수(CNT)를 구한다. 이때 구한 칸의 수는 달라질 수있다. 만약 0행 0열을 기준으로 두지 않고 0행 0열을 바꾸고 시작 했다면, 새로 칠해야 할 칸은 4\*4 - CNT 이다. 예를 들면 초기 주어진 값은 'W'였는데 'B'로 바꾸었다면 기준이 달라지므로 원래 바꾸어야할 칸은 그대로 있고, 바꾸지 않아야할 칸은 모두 바꾸어야할 칸으로 바뀐다.

그리고 바꾸어야할 칸의 수를 세는 알고리즘은 다음과 같다. 시작행, 시작열을 정한다. 시작행, 시작열은 체스판에서 가장 왼쪽, 위 칸으로 0행 0열 부터 N-8행, M-8행까지이다. 이유는 X는 7칸을 이동해서 마지막 칸인 N-1이 될 수 있는 행이다. 식으로 나타내면 X+7 = N-1이 되어야 하므로 X= N-8행이다. 열의 경우도 마찬가지이다.

매 행마다 매열들의 값을 기준값과 비교해서 새로칠해야하는 칸을 체크해주면된다.

시작행, 시작열에서 열의 값을 2칸씩 떨어진곳은 시작행과 같은 색이 칠해져 있어야하고, 시작열+1부터 2칸씩 떨어진 곳은 시작행, 시작열과 다른 색이 칠해져 있어야한다.

Code

import sys  

n = int(input())  

find\_num = int(input())  

table = \[\[0\]\*n for \_ in range(n)\]  
dir\_row = \[-1,0,1,0\]  
dir\_col = \[0,1,0,-1\]  
whar\_dir = 0  
move\_cnt = 1  
cur\_row = n//2  
cur\_col = cur\_row  
cur\_num = 1  
while cur\_num < n\*\*2:  
    for move\_cnt in range(1,n):  
        if move\_cnt == n-1:  
            for \_ in range(3):  
                for \_ in range(move\_cnt):  
                    table\[cur\_row\]\[cur\_col\] = cur\_num  
                    if cur\_num == find\_num:  
                        answer = (cur\_row,cur\_col)  
                    cur\_num += 1  
                    cur\_row += dir\_row\[whar\_dir\]  
                    cur\_col += dir\_col\[whar\_dir\]  
                whar\_dir = (whar\_dir+1)%4  
            else:  
                table\[cur\_row\]\[cur\_col\] = cur\_num  
                if cur\_num == find\_num:  
                    answer = (cur\_row,cur\_col)  
        else:  
            for \_ in range(2):  
                for \_ in range(move\_cnt):  
                    table\[cur\_row\]\[cur\_col\] = cur\_num  
                    if cur\_num == find\_num:  
                        answer = (cur\_row,cur\_col)  
                    cur\_num += 1  
                    cur\_row += dir\_row\[whar\_dir\]  
                    cur\_col += dir\_col\[whar\_dir\]  
                whar\_dir = (whar\_dir+1)%4  
            move\_cnt += 1  

for row in table:  
    print(\*row)  
print(answer\[0\]+1,end=" ")  
print(answer\[1\]+1)