[python] 알고리즘 문제 해결 전략 1권 :: 게임판 덮기 (p159) 문제

6.5 문제 : 게임판 덮기 (문제 ID: BOARDCOVER, 난이도: 하)

문제

H X W 크기의 게임판이 있습니다. 게임판은 검은 칸과 흰 칸으로 구성된 격자 모양을 하고 있는데 이 중 모든 흰 칸을 세 칸짜리 L자 모양의 블록으로 덮고 싶습니다. 이때 블록들은 자유롭게 회전해서 놓을 수 있지만, 서로 겹치거나, 검은 칸을 덮거나, 게임판 밖으로 나가서는 안 됩니다. 다음 그림은 한 게임판과 이를 덮는 방법을 보여줍니다.

게임판이 주어질 때 이를 덮는 방법의 수를 계산하는 프로그램을 작성하세요.

시간 및 메모리 제한

프로그램은 2초 안에 실행되어야 하며, 64MB 이하의 메모리를 사용해야만 합니다.

입력

입력의 첫 줄에는 테스트 케이스의 수 C(C<=30)가 주어집니다. 각 테스트 케이스의 첫 줄에는 두 개의 정수 H,W(1<=H,W<=20)가 주어집니다. 다음 H 줄에 각 W 글자로 게임판의 모양이 주어집니다. #은 검은 칸, .은 흰 칸을 나타냅니다. 입력에 주어지는 게임판에 있는 흰 칸의 수는 50을 넘지 않습니다.

출력

한 줄에 하나씩 흰 칸을 모두 덮는 방법의 수를 출력합니다.

나의 답

import sys
import copy

try:
    c=int(input()) # testcase
    h_w=input()
    blank = int()

    for index in range(0,len(h_w)):
        if h_w[index]==" ":
            blank = index

    h = int(h_w[:blank])
    w = int(h_w[blank+1:])

    row = list()
    for i in range(0,h):
        row.append(input())

    array = list()
    white_sum = int(0)
    net=int(0)

    for i in range(0,h):
        array.append(list())
        for j in range(0,w):
            array[i].append(row[i][j])
            if row[i][j]==".":
                white_sum+=1

    if c>30 or h<1 or h>20 or w<1 or w>20 or white_sum>50:
        raise Exception("range error")

except:
    print("input sys error")
    sys.exit()


def findL(place,tmp_array,map,L):
    tmp_array.append(place)
    if len(tmp_array)==3:
        tmp = copy.deepcopy(tmp_array)
        L.append(tmp)
        tmp_array.pop()
        return

    direction = [[0,1],[1,0],[-1,0],[0,-1]]

    for dir in direction: # 여기서부터
        tmp=[]
        for i in range(0,2):
            tmp.append(dir[i]+place[i])
        if tmp[0]>=0 and tmp[0]<h and tmp[1]>=0 and tmp[1]<w and not(tmp in tmp_array) and map[tmp[0]][tmp[1]]==".":
            if len(tmp_array)==2:
                x1 = tmp_array[0][0]
                y1 = tmp_array[0][1]
                x2 = tmp_array[1][0]
                y2 = tmp_array[1][1]
                if (x1==x2 and x2==tmp[0]) or (y1==y2 and y2==tmp[1]) or (x1!=x2!=tmp[0]) or (y1!=y2!=tmp[1]): # L모양인지 체크
                    continue
            findL(tmp,tmp_array,map,L)
    tmp_array.pop()

def findL_two(place,map,L):

    direction = [[0,1],[1,0],[0,-1],[-1,0]]
    for index in range(0,len(direction)):
        x1 = direction[index][0]+place[0]
        y1 = direction[index][1]+place[1]

        if index==3:
            x2 = direction[0][0]+place[0]
            y2 = direction[0][1]+place[1]
        else:
            x2 = direction[index+1][0]+place[0]
            y2 = direction[index+1][1]+place[1]

        if x1>=0 and x1<=h and y1>=0 and y1<=w and x2>=0 and x2<=h and y2>=0 and y2<=w and map[x1][y1]=="." and map[x2][y2]==".":
            array = list()
            array.append(place)
            array.append([x1,y1])
            array.append([x2,y2])
            L.append(array)

def completeMap(map):
    first_white = list()
    global net 
    global white_sum

    tmp = True
    for j in range(0,h):
        for i in range(0,w):
            if map[j][i]==".":
                tmp = False
                first_white.append(j)
                first_white.append(i)
                break
        if not(tmp):
            break

    L = list()
    array = list()
    print(first_white)
    findL(first_white,array,map,L)
    findL_two(first_white,map,L)
    print(L)

    if not(len(L)):
        return 0

    for l_obj in L:
        for lxy in l_obj:
            map[lxy[0]][lxy[1]]="*"
            white_sum-=1
        print(white_sum)
        print("map1")
        for tmp in map:
            print(tmp)
        if not(white_sum):
            for lxy in l_obj:
                map[lxy[0]][lxy[1]]="."
                white_sum+=1
            return 1
        else:
            done = int(completeMap(map))
            net += done
            done = 0
        for lxy in l_obj:
            map[lxy[0]][lxy[1]]="."
            white_sum+=1
        print(white_sum)
        print("map2")
        for tmp in map:
            print(tmp)
        print("net",net)
    return 0

if not(white_sum%3):
    completeMap(array)
    print("net", net)
else: # 주어진 흰칸이 3의 배수가 아니면 fail
    print(0)
    sys.exit()

설명

​ completeMap 함수는 우선 map이 주어졌을 때 가장 처음 발견된 흰 칸부터 시작해서 해당 칸을 지나는 L모양을 찾는다. L모양 찾기는 함수 2개로 구현하였으며, 첫번째 함수는 해당 칸에서 시작되는 L모양이고 두번째 함수는 해당 칸을 가운데로 하는 L모양이다.

 

왼쪽과 같은 map이 주어졌을 때, 시작 위치는 가장 먼저 발견된 왼쪽 상단의 칸이고, 해당 칸을 포함하는 L모양을 findL, findL_two 함수를 통해 모두 찾으면 다음 세가지가 나온다.

찾은 L모양 3가지를 for문을 통해 차례로 하나씩 map에 채우면서 재귀함수를 이용해 completeMap에 바뀐 map을 넘긴다.

 

왼쪽과 같은 바뀐 map에서 시작 위치를 잡고 방금 전과 같이 L모양을 모두 찾아 다시 for문을 돌면서 하나씩 넣는다.

그러면 다음과 같은 map이 나오는데, 한번 더 재귀함수를 통해 넘기게 되면 해당 위치에서의 L모양을 찾을 수 없고, 그렇다면 실패로 0값을 return 한다.

0을 return 받고 map에서 채웠던 부분을 삭제한 후, 2번째 그림에서의 for문을 계속 진행하여 다른 L 모양을 넣는다.

이러한 방식으로 계속 진행하다가 map이 완전히 채워지는 때에 전역변수 net을 1 증가 시킨다.

문제점

완전 탐색으로 코드를 짜보았는데, 생각보다 코드 짜기가 너무 어려웠다. 아직 재귀함수에서 return 하는 부분이나 전역 변수에 값을 더하는 부분을 제대로 깨닫지 못한 것 같다. 그리고 설계를 대충하고 시작하다보니 구현 시 고쳐야 할 사항들이 많아서 디버깅해보면서 고치는 방식으로 진행하게 되어 푸는데 많은 시간이 걸렸다.

또한 완전 탐색이다 보니 시간이 너무 많이 걸려 1514의 경우의 수가 나오는 마지막 예제의 경우 10분 동안 프로그램을 가동시켜야 답이 나왔다. 답은 정확히 나왔지만 너무 오래 걸려 다른 방법이 있을 것이라고 생각한다.

시간 복잡도

최악의 시간 복잡도를 생각해보면 한 칸에 나올 수 있는 L모양은 최대 12개이다. map에서 벗어나거나 찾을 수 없는 경우도 있으니 가장자리를 제외한 가운데의 흰 칸에서만 진행한다고 가정하면, 흰 칸이 최대 50칸 나올 수 있으므로 88 map일때 최대 42칸 정도로 계산하면 된다. testcase는 최대 50번 실행할 수 있으므로, 12^(42)*50 이 최악의 시간 복잡도가 되며, 너무 크다.

메모리

Partition of a set of 140556 objects. Total size = 10300278 bytes.
Index Count % Size % Cumulative % Kind (class / dict of class)
0 45997 33 3304049 32 3304049 32 str
1 34808 25 1467312 14 4771361 46 tuple
2 17281 12 1026153 10 5797514 56 bytes
3 8667 6 730096 7 6527610 63 types.CodeType
4 1395 1 670536 7 7198146 70 type
5 8044 6 579168 6 7777314 76 function
6 2115 2 505916 5 8283230 80 dict (no owner)
7 1395 1 405012 4 8688242 84 dict of type
8 361 0 291624 3 8979866 87 dict of module
9 367 0 150860 1 9130726 89 set
<381 more rows. Type e.g. '_.more' to view.>

 

testcase 3개는 너무 시간이 오래걸려서 (마지막 testcase가) 2번째 것만 돌려봣는데 10GB 정도의 메모리를 사용하였다. 마지막 testcase는 훨씬 많은 메모리를 사용할 것으로 보인다.

주어진 답과 다른 점

​ 왼쪽 위부터로 순서를 강제하여 구현하는 것은 같았으나, 본인은 현재 칸을 포함하는 L모양을 만들 수 있는 모든 경우의 수를 생각했다. 따라서 한 칸 당 12개의 경우의 수가 필요했다. 심지어 처음에는 findL(8개), findL_two(4개) 두개의 함수로 나누어서 구했는데, 잘못됨을 깨닫고 고치긴했다.

​ 고친 코드는 direction에서 애초에 해당하지 않는 부분(*이거나 map에서 벗어나거나)들을 지우는 방식으로 진행하였으나, 이전 코드와 비슷한 결과를 냈다.

​ 주어진 답에서는 왼쪽 위부터라는 순서를 강제하면 다음과 같은 4가지 경우의 수만 나온다고 설명하고 있다.

원래는 중간 칸을 생각해서 모든 경우의 수를 따져야한다고 생각했으나, 왼쪽 위부터 채워 나가면 어차피 똑같은 조건이 되므로 4가지 경우의 수만 따지면 된다.

​ 이렇게 L모양 찾기에서 많은 시간을 할애한 코드를 한번에 4가지 경우의 수만 따지면 되는 코드로 변환한다면 복잡도가 대폭 감소할 것으로 보인다.

 

​ 또한 L 모양 하나를 찾는다는 것을 한 조각으로 보는 데에는 성공했지만, 전체 L모양의 갯수를 N으로 취급하여 N개의 조각이 전체를 완성한다는 생각은 하지 못하고 코드를 짰다. 따라서 시간 복잡도를 구하는 방식도 수정해야할 것이다.

​ 주어진 답에서는 4개의 경우의 수가 최대 [50/3] = 16개의 블록마다 존재하기 때문에 4의 16승 즉, 2의 32개를 답의 상한으로 계산하였다.

 

​ 본인은 흰 칸이 없어지는 경우(map이 모두 덮히는 경우)를 white_sum이라는 변수를 두어 계속 변경시키는 코드로 구현했다.

​ 주어진 답에서는 처음에 왼쪽 상단의 흰 칸을 찾는 과정에서 흰 칸을 찾을 수 없으면 map이 완성되었다고 판단하게 구현했다. 하나의 상황을 두 가지 변수로 나누어 나타내는 것보다 이와 같은 방식이 더 정확할 것 같다.

 

​ 본인은 칸을 .과 *을 이용하여 구현하여서 채울 때는 *를 치울 때는 .를 덮어씌우면서 코드를 진행하였다. 따라서 겹치는 것을 미리 파악한 후에 겹치지 않는 블록만 채워야해서 채우기 전 조건을 판단하는 과정이 많다.

​ 주어진 답에서는 숫자를 이용하여 겹치는 칸도 2라는 숫자로 표현할 수 있게 하였다. 따라서 우선적으로 블록을 채운 후에 판단 가능하다. 이는 map을 더 자주 변화시켜서 좋다고 보긴 힘든 것 같다.