[SWEA / PYTHON] 14413. 격자판 칠하기

import os
import sys


current_file = os.path.basename(__file__)[:-3]
sys.stdin = open(f"input/{current_file}_input.txt", "r", encoding="utf-8-sig")


result = []

T = int(input())


def check_valid():
    global N, M

    start_y = -1
    start_x = -1
    if "#" in arr[0]:
        start_x = arr[0].index("#")
        start_y = 0
    elif "." in arr[0]:
        start_x = arr[0].index(".")
        start_y = 0
    else:
        for i in range(1, N):
            if "#" in arr[i]:
                start_x = arr[i].index("#")
                start_y = i
                break
            elif "." in arr[i]:
                start_x = arr[i].index(".")
                start_y = i
                break

    if start_x == -1 or start_y == -1:
        return True

    char = arr[start_y][start_x]

    if abs(start_x - start_y) % 2 == 0:
        for y in range(N):
            if y % 2 == 0:
                for x in range(0, M, 2):
                    if arr[y][x] != "?" and arr[y][x] != char:
                        return False
                for x in range(1, M, 2):
                    if arr[y][x] == char:
                        return False
            else:
                for x in range(1, M, 2):
                    if arr[y][x] != "?" and arr[y][x] != char:
                        return False
                for x in range(0, M, 2):
                    if arr[y][x] == char:
                        return False
    else:
        for y in range(N):
            if y % 2 == 0:
                for x in range(1, M, 2):
                    if arr[y][x] != "?" and arr[y][x] != char:
                        return False
                for x in range(0, M, 2):
                    if arr[y][x] == char:
                        return False
            else:
                for x in range(0, M, 2):
                    if arr[y][x] != "?" and arr[y][x] != char:
                        return False
                for x in range(1, M, 2):
                    if arr[y][x] == char:
                        return False

    return True


for case in range(1, T + 1):
    N, M = map(int, input().split())

    arr = list(list(input()) for _ in range(N))

    P = check_valid()

    if P:
        result.append(f"#{case} possible")
    else:
        result.append(f"#{case} impossible")


for _ in result:
    print(_)


output = open(f"input/{current_file}_output.txt", "r").readlines()
output = [line.strip() for line in output]

print("------------------- 오답 ------------------ ( 이 아래로 출력이 없으면 정답)")

for r, o in zip(result, output):
    if r != o:
        print(f"정답 : {o},     오답 : {r}")

풀이.

가장 처음 접근 방법은 브루트 포스로, dfs 로 모든 경우의 수를 하나하나 비교 하려고 했다.
dfs 로 문제를 풀었을 땐, 예제는 통과 했지만 실제 제출에서는 런타임 에러가 발생했다.

아마, 재귀에서 최대 범위를 넘어가기 때문에 발생하지 않을까 생각된다.
SWEA 는 sys를 임포트 할 수 없으므로, 공식으로 해결했다.

다르게 생각하니 생각보다 매우 쉬운 문제였다.

다르게 생각하는 방법을 기르자!!