무식하게 풀기(brute-force) (2)

• 저번 글에 이어서 브루트포스 관련 추가적인 문제와 최적화에 관한 내용을 다루어 보겠습니다!

 

문제: 게임판 덮기

• H X W 크기의 게임판에서, 모든 흰 칸을 L자 모양의 블록으로 덮는 방법을 찾는 문제입니다.
• 블록은 회전 가능하지만, 겹치거나 검은 칸을 덮거나 게임판 밖으로 나갈 수는 없습니다.
• 프로그램은 2초 안에 실행되어야 하며, 64MB 이하의 메모리를 사용해야 합니다!

• 입력은 테스트 케이스 수 $C$($C$≤$30$), 또한 각 테스트 케이스마다 두 정수 $H$, $W$($1$≤$H$, $W$≤$20$)와 $H\times T$ 크기의 게임판(흰 칸의 수는 최대 50)으로 구성됩니다.
• 게임판을 구성할 때 검은 칸은 '#', 흰 칸은 '.'으로 표시됩니다.

3
3 7
#.....#
#.....#
##...##
3 7
#.....#
#.....#
##..###
8 10
##########
#........#
#........#
#........#
#........#
#........#
#........#
##########

• 출력 값은 한 줄에 하나씩 흰 칸을 모두 덮을 수 있는 방법의 수입니다.

0
2
1514

 

풀이: 게임판 덮기

• 주어진 게임판의 모든 흰 칸을 L자 모양의 블록으로 덮기 위해 먼저 흰 칸의 수가 3의 배수가 아니면 블록으로 덮을 수 없으므로 이 경우는 제외합니다.
• 그 다음에는 가능한 모든 블록의 배치를 탐색하는 재귀 호출 방식을 사용합니다.
• 이때 중요한 것은 같은 배치를 여러 번 세는 것을 방지하기 위해, 가장 왼쪽 위에 있는 빈 칸부터 블록으로 덮는 것입니다.
• 블록을 놓는 방법은 총 네 가지가 있으며, 각 방법은 블록이 차지하는 칸들의 상대적 위치로 정의됩니다.
• 블록을 놓거나 치울 때는 이 상대적 위치를 사용하여 처리합니다. 만약 블록을 놓을 수 없는 경우가 발생하면, 그 부분은 무시하고 다른 배치를 시도합니다.
• 실제로는 이론적으로 가능한 경우의 수보다 훨씬 적은 수의 유효한 배치가 존재하므로, 재귀 호출은 실제로 실행 가능한 시간 내에 문제를 해결할 수 있습니다.

# 게임판 덮기 문제를 해결하는 재귀 호출 알고리즘

# 주어진 칸을 덮을 수 있는 네 가지 방법
# 블록을 구성하는 세 칸의 상대적 위치 (dy, dx)의 목록
cover_type = [
    [[0, 0], [1, 0], [0, 1]],
    [[0, 0], [0, 1], [1, 1]],
    [[0, 0], [1, 0], [1, 1]],
    [[0, 0], [1, 0], [1, -1]]
]
# board의 (y, x)를 type번 방법으로 덮거나, 덮었던 블록을 없앱니다.
# delta = 1이면 덮고, -1이면 덮었던 블록을 없앱니다.
# 만약 블록이 제대로 덮이지 않은 경우 (게임판 밖으로 나가거나, 겹치거나, 검은 칸을 덮을 때) False를 반환합니다.
def set_board(board, y, x, type, delta):
    ok = True
    for i in range(3):
        ny = y + cover_type[type][i][0]
        nx = x + cover_type[type][i][1]
        if ny < 0 or ny >= len(board) or nx < 0 or nx >= len(board[0]):
            ok = False
        else:
            board[ny][nx] += delta
            if board[ny][nx] > 1:
                ok = False
    return ok
# board의 모든 빈 칸을 덮을 수 있는 방법의 수를 반환합니다.
# board[i][j] = 1 : 이미 덮인 칸 혹은 검은 칸
# board[i][j] = 0 : 아직 덮이지 않은 칸
def cover(board):
    # 아직 채우지 못한 칸 중 가장 윗줄 왼쪽에 있는 칸을 찾습니다.
    y, x = -1, -1
    for i in range(len(board)):
        for j in range(len(board[i])):
            if board[i][j] == 0:
                y, x = i, j
                break
        if y != -1:
            break
    # 기저 사례: 모든 칸을 채웠으면 1을 반환합니다.
    if y == -1:
        return 1
    ret = 0
    for type in range(4):
        # 만약 board[y][x]를 type 형태로 덮을 수 있으면 재귀 호출합니다.
        if set_board(board, y, x, type, 1):
            ret += cover(board)
        # 덮었던 블록을 치웁니다.
        set_board(board, y, x, type, -1)
    return ret

 

최적화 문제

• 최적화 문제는 단순히 정답을 찾는 것을 넘어서, 가능한 여러 해답 중에서 '가장 좋은' 해답을 선택해야 하는 문제를 말합니다.
• 예를 들어, 여러 개의 사과 중에서 몇 개를 골라 그 무게의 합을 최대화하거나, 무게 차이를 최소화하는 문제와 같이, 특정 기준에 따라 최적의 해답을 찾아야 합니다.
• 최적화 문제를 해결하는 방법은 여러 가지가 있지만, 가장 기본적인 방법은 '완전 탐색'입니다.
• 완전 탐색은 직관적이며, 모든 가능한 경우를 고려하기 때문에 확실히 최적의 해답을 찾을 수 있다는 장점이 있습니다.
• 하지만, 가능한 해답의 수가 매우 많을 경우 시간이 많이 걸릴 수 있다는 단점도 있습니다.

 

예제: 여행하는 외판원 문제

• 여행하는 외판원 문제(Traveling Sales-man Problem, TSP)는 최적화 문제의 가장 대표적인 예시 중 하나로, 여러 도시를 한 번씩 방문하고 출발 도시로 돌아오는 가장 짧은 경로를 찾는 문제입니다.
• 각 도시는 직선 도로로 연결되어 있다고 가정하며, 이 문제는 도시들을 방문하는 순서에 따라 총 여행 거리가 달라질 수 있습니다.
• 완전 탐색으로 이 문제를 접근해볼 수 있습니다! 시작 도시를 정한 후, 나머지 도시들을 방문하는 모든 순서를 고려해야 합니다.
• 예를 들어, 10개의 도시가 있다면, 가능한 모든 경로는 9!, 즉 362880개입니다.
• 이는 컴퓨터가 1초 안에 계산할 수 있는 범위 내이기 때문에, 완전 탐색 방법이 실제로 실행 가능합니다.

 

• 더 효율적인 해결을 위해, 재귀 호출을 사용하여 각 단계에서 한 도시씩 경로에 추가하는 방식으로 문제를 접근할 수 있습니다.
• 이는 'path'라는 인자를 사용하여 현재까지의 경로를 저장하고, 나머지 도시들을 방문하는 데 필요한 최소 거리를 계산하는 함수를 구현함으로써 이루어집니다.
• 이 과정에서, 각 도시의 방문 여부와 현재 경로의 길이를 효율적으로 관리하기 위해, 추가적인 boolean 배열과 현재 경로 길이를 인자로 사용합니다.

# 여행하는 외판원 문제를 해결하는 재귀 호출 알고리즘

n = 0  # 도시의 수
dist = []  # 두 도시 간의 거리를 저장하는 배열
# path: 지금까지 만든 경로
# visited: 각 도시의 방문 여부
# currentLength: 지금까지 만든 경로의 길이
# 나머지 도시들을 모두 방문하는 경로들 중 가장 짧은 것의 길이를 반환합니다.
def shortest_path(path, visited, current_length):
    global n, dist
    # 기저 사례: 모든 도시를 다 방문했을 때는 시작 도시로 돌아가고 종료합니다.
    if len(path) == n:
        return current_length + dist[path[0]][path[-1]]
    result = float('inf')  # 매우 큰 값으로 초기화
    # 다음 방문할 도시를 전부 시도해 봅니다.
    for next in range(n):
        if visited[next]:
            continue
        here = path[-1]
        path.append(next)
        visited[next] = True
        # 나머지 경로를 재귀 호출을 통해 완성하고 가장 짧은 경로의 길이를 얻습니다.
        cand = shortest_path(path, visited, current_length + dist[here][next])
        result = min(result, cand)
        visited[next] = False
        path.pop()
    return result

 

문제: 시계 맞추기

• 시계 맞추기 문제는, 4x4 격자 형태에 배치된 열여섯 개의 시계가 모두 12시를 가리키도록 만드는 것입니다.
• 각 시계는 12시, 3시, 6시 또는 9시 중 하나를 가리키고 있으며, 이를 조정하기 위해서는 열 개의 스위치를 사용해야 합니다.
• 각 스위치는 세 개에서 다섯 개의 시계에 연결되어 있으며, 스위치를 누를 때마다 연결된 시계들은 3시간씩 앞으로 진행됩니다.

스위치 번호	연결된 시계들	스위치 번호	연결된 시계들
0	0, 1, 2	5	0, 2, 14, 15
1	3, 7, 9, 11	6	3, 14, 15
2	4, 10, 14, 15	7	4, 5, 7, 14, 15
3	0, 4, 5, 6, 7	8	1, 2, 3, 4, 5
4	6, 7, 8, 10, 12	9	3, 4, 5, 9, 13

• 문제는 모든 시계를 12시로 맞추기 위해 스위치를 눌러야 하는 최소 횟수를 계산해야 합니다.
• 프로그램은 10초 안에 실행되어야 하며, 64MB 이하의 메모리를 사용해야 합니다!

2
12 6 6 6 6 6 12 12 12 12 12 12 12 12 12 12
12 9 3 12 6 6 9 3 12 9 12 9 12 12 6 6

• 예를 들어, 첫 번째 예제는 8번 스위치를 두 번 누름으로써 해결할 수 있지만, 다른 예제들은 더 많은 스위치 조작을 필요로 할 수 있습니다.

2
9

 

풀이: 시계 맞추기

• 이 문제에서 중요한 점은 스위치를 누르는 순서가 결과에 영향을 주지 않는다는 점입니다.
• 즉, 우리가 해야 할 일은 각 스위치를 몇 번 누를지 결정하는 것뿐입니다.
• 그러나 한 가지 문제가 있습니다. 이론상으로는 스위치를 무한히 누를 수 있기 때문에 가능한 모든 조합을 열거하는 것은 불가능해 보입니다!
• 그렇지만 시계의 특성, 즉 12시간이 지나면 시계가 원래 상태로 돌아온다는 점을 활용하면, 문제를 유한한 범위 내에서 해결할 수 있습니다.
• 어떤 스위치든지 네 번 누르면 원점으로 돌아오므로, 실제로는 각 스위치를 최대 세 번까지만 누를 수 있는 것입니다.
• 이로 인해 각 스위치에 대해 네 가지 가능성(0번, 1번, 2번, 3번 누름)만 고려하면 되므로, 전체 경우의 수는 $4^{10}$, 즉 1048576가지로 줄어듭니다. 이는 충분히 계산할 수 있는 범위입니다.

 

• 이 문제를 해결하기 위해 스위치를 누르는 모든 횟수의 조합을 시도하면서, 각 경우에 대해 모든 시계가 12시를 가리키는지 확인하는 재귀 함수로 구현할 수 있습니다.
• 이 과정에서 만약 모든 시계를 12시로 맞출 수 없는 경우, 함수는 매우 큰 값을 반환하여 그 경우를 제외시킵니다.
• 횟수가 매우 큰 값인 경우에는 모든 시계를 12시로 맞출 수 없다는 의미이므로, 이때는 -1을 출력합니다.

# 시계 맞추기 문제를 해결하는 완전 탐색 알고리즘

INF, SWITCHES, CLOCKS = 987654321, 10, 16
# linked[i][j] = 'x': i번 스위치와 j번 시계가 연결되어 있습니다.
# linked[i][j] = '.': i번 스위치와 j번 시계가 연결되어 있지 않습니다.
linked = [
    "xxx.............",
    "...x...x.x.x....",
    "....x.....x...xx",
    "x...xxxx........",
    "......xxx.x.x...",
    "x.x...........xx",
    "....xx.x......xx",
    ".xxxxx..........",
    "...xxx...x...x.."
]
# 모든 시계가 12시를 가리키고 있는지 확인합니다.
def are_aligned(clocks):
    return all(clock == 12 for clock in clocks)
# switch번 스위치를 누릅니다.
def push_switch(clocks, switch):
    for clock in range(CLOCKS):
        if linked[switch][clock] == 'x':
            clocks[clock] += 3
            if clocks[clock] == 15:
                clocks[clock] = 3
# clocks: 현재 시계들의 상태
# switch: 이번에 누를 스위치의 번호
# 위 두 변수가 주어질 때, 남은 스위치들을 눌러서 clocks를 12시로 맞출 수 있는 최소 횟수를 반환합니다.
# 만약 불가능하다면 INF 이상의 큰 수를 반환합니다.
def solve(clocks, switch):
    if switch == SWITCHES:
        return 0 if are_aligned(clocks) else INF
    # 이 스위치를 0번 누르는 경우부터 세 번 누르는 경우까지를 모두 시도합니다.
    result = INF
    for cnt in range(4):
        result = min(result, cnt + solve(clocks, switch + 1))
        push_switch(clocks, switch)
    push_switch(clocks, switch)
    # push_switch(clocks, switch)가 네 번 호출되었으니 clocks는 원래와 같은 상태가 됩니다.
    return result

 

많이 등장하는 완전 탐색 유형

모든 순열 만들기

• 서로 다른 N개의 원소로 만들 수 있는 모든 순열은 N개의 원소를 일렬로 나열한 것입니다.
• 예를 들어, 원소가 [1, 2, 3]인 경우, 가능한 순열은 [1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1] 등입니다.
• 이렇게 N개의 원소로 만들 수 있는 순열의 총 개수는 N!입니다.
• 하지만, N의 값이 10을 넘어가면, 시간 안에 모든 순열을 생성하는 것은 현실적으로 어려워집니다.

 

모든 조합 만들기

• 서로 다른 N개의 원소 중에서 R개를 고르는 것을 조합이라고 합니다.
• 조합은 순서를 고려하지 않기 때문에, [1, 2, 3]에서 2개를 고르는 경우 [1, 2]와 [2, 1]은 같은 조합으로 간주됩니다.
• 조합의 총 개수는 이항 계수 $ \binom{N}{R}$로 표현되며, 이는 재귀 호출을 통해 구현할 수 있습니다.

 

$2^n$가지 경우의 수 만들기

• n개의 질문에 대한 답이 '예' 또는 '아니오'일 때, 가능한 모든 답의 조합은 $2^n$가지입니다.
• 이런 조합들은 각각을 n 비트의 정수로 생각해 간단한 1차원 for문을 사용하여 모두 생성할 수 있습니다.