자료구조 - 완전탐색(Brute-Force-Search) 학습_2

완전탐색 (Brute-Force-Search) 문제 2 - Boardcover

  • height(H) * width(W)의 보드가 검은색과 흰색으로 채워져 있다.
  • 모든 흰칸을 ‘ㄱ’ 모양의 흰색 블록으로 덮고 싶다.
  • 블록은 회전 가능하지만 겹치거나 검은색 블록을 침범하거나 밖으로 이탈되어서는 안된다.
  • 보드가 있을 때 이를 덮는 방법의 수를 계산하는 프로그램을 만드시오.
  • 알고리즘 문제해결 전략 p.159 게임판 덮기

코드 구현 및 해설

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
# Height = 8
H = 8
# Width = 10
W = 10
board = [
    [1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
    [1, 0, 0, 0, 0, 0, 0, 0, 0, 1],
    [1, 0, 0, 0, 0, 0, 0, 0, 0, 1],
    [1, 0, 0, 0, 0, 0, 0, 0, 0, 1],
    [1, 0, 0, 0, 0, 0, 0, 0, 0, 1],
    [1, 0, 0, 0, 0, 0, 0, 0, 0, 1],
    [1, 0, 0, 0, 0, 0, 0, 0, 0, 1],
    [1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
]

# cases = 4가지 블록 타입(-> [y, x] 형태)
#   type1     type2     type3     type4
#  [*][ ]    [*][ ]    [*]          [*]    
#  [ ]          [ ]    [ ][ ]    [ ][ ] 
cases = [
    [[1, 0], [0, 1], [0, 0]],  
    [[0, 1], [1, 1], [0, 0]],
    [[1, 0], [1, 1], [0, 0]],
    [[1, 0], [1, -1], [0, 0]]
]

# [y, x] 위치가 보드를 벗어났는지를 판단하는 함수
def out_range(y, x):
    if (y < 0  or x < 0 or H <= y or W <= x):
        return True
    return False

# 현재위치(=board[y][x])에 c 타입의 흰색 블록을 채워넣는 함수
def put(y, x, c):
    # c(for c in cases에서의 c) : 흰색 블록 타입
    ret = True
    # 특정 흰색 블록 타입의 point(=[y, x]) --> point[0] = y, point[1] = x 
    for point in c:
        # 현재 위치 y에서 채워넣을 특정 블록의 y 값 추가
        _y = y + point[0]
        # 현재 위치 x에서 채워넣을 특정 블록의 x 값 추가
        _x = x + point[1]
        # _y, _x가 검은색 블록 테두리 위치에서 벗어난 경우 ret = False
        if out_range(_y, _x):
            ret = False
        # _y, _x가 검은색 블록 테두리 안에 위치할 경우
        else:
            # board[_y][_x] 위치에 값 1 증대
            board[_y][_x] += 1
            # board[_y][_x] 위치의 값이 1 이상일 경우, ret = False
            if board[_y][_x] > 1:
                ret = False

    # 채워 넣을 흰색 블록이 검은색 블록 테두리 안에 있고, 기존 흰색 블록과 겹치지 않는다면 True 반환
    # 채워 넣을 흰색 블록이 검은색 블록 테두리 위치를 벗어나 있거나, 기존 흰색 블록과 겹친다면 False 반환
    return ret

# 현재위치(=board[y][x])에서 c 타입의 흰색 블록을 제거하는 함수
def get(y, x, c):
    for point in c:
        _y = y + point[0]
        _x = x + point[1]
        # _y, _x 위치가 검은색 블록 테두리를 벗어났다면 continue
        if out_range(_y, _x):
            continue
        # _y, _x 위치가 검은색 블록 테두리 안에 있다면, board[_y][_x] 값 1 차감
        else:
            board[_y][_x] -= 1

def solve():
    # base case
    fx = fy = None
    for i in range(H):
        # for j in range(10):
        for j in range(W):
            if board[i][j] == 0:
                fy = i
                fx = j
                break

        if fx != None:
            break

    # 흰색 블록이 빈 부분 없이 꽉 채워져 있는 경우, return 1
    if fx == None:
        return 1

    # 흰색 블록이 채워질 공간이 있는 경우
    ret = 0
    
    for c in cases:         
        # 특정 흰색 블록 타입이 들어갈 공간이 있으면, 블록 집어넣고 재귀함수 호출 (블록 채워지지 않은 위치에서 다시 solve() 실행)
        if put(fy, fx, c):
            ret += solve()
        # 블록 들어갈 공간 없으면, board의 [fy, fx] 위치에서 c 타입 제거 후, 그 다음 c 타입이 들어갈 공간이 있는지 확인
        get(fy, fx, c)

    # 모든 블록 타입이 들어갈 공간 없으면, return 0
    # 모든 블록이 흰색으로 채워질 경우, ret += 1
    return ret

print(solve())
Posted