[swea] 14413번: 격자판 칠하기 - 파이썬(python)

T = int(input())
for t in range(1, T+1):
    n, m = map(int, input().split())
    arr = []
    for _ in range(n):
        arr.append(list(input()))

    board = [0,0,0,0]
    for x in range(n) :
        for y in range(m) :
            if arr[x][y] == "#" :
                if (x+y) % 2 == 0 :
                    board[0] += 1
                else :
                    board[1] += 1

            elif arr[x][y] == "." :
                if (x+y) % 2 == 0 :
                    board[2] += 1
                else :
                    board[3] += 1
    if (board[0] != 0 and board[1] != 0) or (board[0] != 0 and board[2] != 0) or(board[2] != 0 and board[3] != 0) or (board[1] != 0 and board[3] != 0) :
        answer = "impossible"
    else :
        answer = "possible"
    
    print(f'#{t} {answer}')

체크모양의 보드를 만들기 위한 규칙을 생각해서 푼 문제..!

같은 모양이 인접한 곳에 겹치지 않으려면,

# 가 있는 (x,y) 의 합이 홀수라면 -> . 가 있는 (x,y) 의 합은 짝수 에만 있어야 한다.

혹은

# 가 있는 (x,y) 의 합이 짝수라면 -> . 가 있는 (x,y) 의 합은 홀수 에만 있어야 한다.\

 

# . #

. # .

# . #

와 같은 보드를 생각해보자.

# 는 (0,0) (0,2) (1,1) (2,0) (2,2) 로 x+y 의 합이 모두 짝수인 곳에만 존재하고,

반대로 .은 x+y 의 합이 모두 홀수인 곳에만 존재한다.

따라서 이 조건을 하나라도 어긴다면, impossible 을 출력해주면 된다.

 

 

이와 같이 x+y 의 홀수/짝수를 따지는 규칙은 유용하게 쓰일 수 있으므로 외워두면 좋을 것 같다!