[Python][SWEA] 14413. 격자판 칠하기 D3

 

 

SW Expert Academy

 

---

🗒️ 파이썬 코드 풀이

def grid(type1,type2) :
    for i in range(N):
        for j in range(M) :
            if lst[i][j] == '?' : continue # "?"인 값은 제외
            if (i+j)%2 == 0 : # i+j가 짝수인 경우
                if lst[i][j] != type1: # 각 case와 일치하지 않는 경우
                    return False
            else :
                if lst[i][j] != type2:
                    return False
    return True

T = int(input())
for tc in range(1,T+1):
    N, M = map(int, input().split())
    lst = [list(input()) for _ in range(N)]  # 격자판 입력

    state1 = grid("#",".") # case1
    state2 = grid(".", "#") # case2

    if state1 or state2 :  # case1 또는 case2가 True인 경우
        print(f"#{tc} possible")
    else:
        print(f"#{tc} impossible")

(0,0)      (0,1)       (0,2)     

(1,0)      (1,1)       (1,2)     

(2,0)      (2,1)       (2,2)     

 

 

1. 배열판의 규칙만 알면, 간단하게 해결 가능하다.

 

2. i+j가 짝수이거나 홀수일 때 조건에 맞는 격자판을 칠할 수 있다.

 

3. 격자판에 "?"라는 변수가 있다. 그렇기 때문에 각 좌표에 어떤 색이 올지 모른다. 

따라서 2가지의 경우로 나눠줬고, 반복적이기 때문에 함수로 만들어줬다.

 

4.  grid 함수

- i,j 위치에서 값이 "?" 인 경우는 생략

- i+j가 짝수인데, 가정한 값과 일치 하지 않는 경우 바로 False 리턴 (홀수 부분도 마찬가지)

- 모든 조건문을 다 통과하면 True 리턴

 

5. 각각의 경우를 grid함수의 매개변수로 넣어주고, 리턴값을 state값에 저장

 

6. state1과 state2 중 한개라도 맞으면 True 

 

📌 나의 풀이 방식

def decision(type1,type2) :
    
    # ?인 경우는 제외해야 함 (type1=type2=? 인 경우는 모두 물음표)
    if type1 == type2 == "#":
        return "impossible"
    elif type1 == type2 == ".":
        return "impossible"

    for i in range(N):
        if i % 2 == 0:
            for j in range(0,M,2):
                if lst[i][j] == "?" : continue  # "?"인 경우는  생략
                if lst[i][j] != type1: 
                    return "impossible"
            for j in range(1,M,2):
                if lst[i][j] == "?": continue
                if lst[i][j] != type2:
                    return "impossible"

        elif i % 2 == 1:
            for j in range(0,M,2):
                if lst[i][j] == "?": continue
                if lst[i][j] != type2:
                    return "impossible"
            for j in range(1,M,2):
                if lst[i][j] == "?": continue
                if lst[i][j] != type1:
                    return "impossible"
    return "possible"

T = int(input())
for tc in range(1,T+1) :
    N,M = map(int,input().split())
    lst = [list(input()) for _ in range(N)]
    type1=type2="?"

    for i in range(N):
        if i % 2 == 0: # 0,2,4,6.... 행
            for j in range(0,M,2): # 0,2,4,6... 열
                if lst[i][j] != "?":
                    type1 = lst[i][j]
            for j in range(1,M,2):  # 1,3,5,7... 열
                if lst[i][j] != "?":
                    type2 = lst[i][j]

        elif i % 2 == 1: # 1,3,5,7...행
            for j in range(0,M,2):
                if lst[i][j] != "?":
                    type2 = lst[i][j]
            for j in range(1,M,2): 
                if lst[i][j] != "?":
                    type1 = lst[i][j]

    ans = decision(type1, type2)
    print(f"#{tc} {ans}")

딱 봐도 엄청 지저분하다...   근데 코드 내용은 간단하다.

우선 나는 i+j가 짝수 홀수로 나뉘는 규칙을 발견하지 못했다.

 

내가 발견한 규칙으로 나눈 것은 다음과 같다

1.  1,3,5,7.... 행 

        1-1    1,3,5,7... 열

        1-2    0,2,4,6... 열

 

2.  0,2,4,6.... 행 

        2-1    1,3,5,7... 열

        2-2    0,2,4,6... 열

 

여기서 부터 코드가 벌써 길어진다..... 

 

거기에 더해, 나는 #과 "."를 굳이 하나씩 찾아줬다.  그 찾아준 값을 decision 함수 매개 변수에 넣어준 것이다.

그냥 case를 2개로 나누면 되는건데....

이렇게 하다보니,  중복되는 코드가 엄청 많은 최고의 비효율 코드가 탄생했다. 

 

(+ 66번째 테스트 케이스에 오류가 발생했는데, 그 경우는 모두 "?"인 경우인 것 같다.  이 경우도 고려해 함수 맨 첫문장에 예외를 구체적으로 작성했다. )

 

🧐 문제 코멘트

음.... 무식하게 풀었다. 정말로 ㅜㅜ

뭐 시험 볼 때 규칙이 생각 안나면 이렇게라도 해야겠지만, 그래도 이렇게 하는 것은 꽤나 리스크가 크다.

내가 생각지 못한 변수들이 많았기 때문이다... 

저런 격자판의 규칙은 꼭 있으니, 규칙성을 먼저 찾아보자 !

---

📚 문제

 

N X M 크기의 직사각형 격자판이 있다. 격자판의 각 칸은 1 x 1 크기의 정사각형 모양이다. 당신은 이 격자판의 각 칸을 검은색 또는 흰색으로 칠할 계획이다.

당신은 격자판의 칸 중 몇 개(0개 이상 NM개 이하)는 검은색으로 칠할지 흰색으로 칠할지를 이미 정해 놓았다. 정확히 표현하자면, N X M 크기의 행렬 A가 있어서, Ai,j 가 ‘#’라면 격자판의 i행 j열에 있는 칸은 검은색으로 칠해야 하고, Ai,j 가 ‘.’라면 격자판의 i행 j열에 있는 칸은 흰색으로 칠해야 하며, Ai,j 가 ‘?’라면 격자판의 i행 j열에 있는 칸은 검은색으로 칠해도 되고 흰색으로 칠해도 된다.

당신은 아직 색이 정해지지 않은 칸들을 어떤 색으로 칠할지를 잘 정한 뒤 격자판을 색칠할 것이다. 색칠한 결과 격자판의 인접한 (즉, 변 하나를 공유하는) 두 칸의 색이 항상 다르게 할 수 있는지를 판단하는 프로그램을 작성하라.

[입력]

첫 번째 줄에 테스트 케이스의 수 T가 주어진다.

각 테스트 케이스의 첫 번째 줄에는 두 개의 자연수 N과 M(1 ≤ N ≤50, 1 ≤ M ≤ 50)이 공백 하나를 사이로 두고 주어진다. 다음 N개의 줄에는 '#', '.', '?'로만 구성된 길이가 M인 문자열이 하나씩 주어지며, 이는 행렬 A를 나타낸다.

[출력]

각 테스트 케이스마다, '?'에 해당하는 칸의 색을 잘 정하여, 격자판의 인접한 두 칸의 색이 항상 서로 다르게 할 수 있다면 ‘possible’을, 그렇지 않다면 ‘impossible’을 출력한다.