18430. 무기 공학 (Python)

18430번: 무기 공학

 

풀이

 백트래킹을 이용하여 해결할 수 있는 문제다. 함수를 호출할 때 받는 매개변수의 인덱스는 부메랑의 중심을 기준으로 한다. 

 위의 그림과 같은 4개의 부메랑 형태 각각을 만들 수 있는지 체크하여 만들 수 있을 경우 해당 부메랑의 강도의 합을 구하고 다음 인덱스로 넘겨 같은 과정을 반복한다. 마지막 인덱스를 벗어났을 경우 현재까지 구한 부메랑 강도의 합을 비교하여 최댓값을 가져오도록 구현하면 된다.

 아래 코드에서 인덱스를 하나의 숫자로 바꾸어 사용하였는데 (행, 열)의 형태로 사용해도 괜찮으나 조금 더 쉽게 표현할 수 있게 1차원으로 표현하였다. 예를 들어 N=3, M=4 일 경우 각 (행, 열)에 해당하는 인덱스는 다음과 같다.

 

 

코드

# x행 y열을 idx로 변환하기 위한 함수
def calcIdx(x, y):
    return x * M + y


# idx: 현재 (행 ,열) 위치의 인덱스, sum: 지금까지 만든 부메랑들의 강도의 합
def solve(idx, sum):
    if idx == N * M:  # 마지막에 도달했을 때
        global res
        res = max(res, sum)  # 최댓값을 갱신하고 탐색 종료
        return

    if check[idx]:  # 이미 부메랑을 만드는 데 사용된 칸일 경우에는 탐색 종료
        return

    # 현재 idx에 대한 행과 열
    x = idx // M
    y = idx % M

    # 현재 idx를 기준으로 오른쪽(east), 왼쪽(west), 아래쪽(south), 위쪽(north)에 대한 idx
    eastIdx = calcIdx(x, y+1)
    westIdx = calcIdx(x, y-1)
    southIdx = calcIdx(x+1, y)
    northIdx = calcIdx(x-1, y)

    # ㅁㅁ
    # ㅁ   형태의 부메랑을 만들 수 있는지 확인
    if (x+1 < N and not check[southIdx]) and (y+1 < M and not check[eastIdx]):
        # 만들 수 있을 경우 해당 칸들을 사용했음을 체크하고
        # 현재 idx 이후부터 마지막 idx까지 반복적으로 호출
        check[idx] = True
        check[southIdx] = True
        check[eastIdx] = True
        for i in range(idx+1, N*M+1):
            solve(i, sum + (board[x][y]*2 + board[x+1][y] + board[x][y+1]))
        check[southIdx] = False
        check[eastIdx] = False
        check[idx] = False

    # ㅁㅁ
    #  ㅁ  형태의 부메랑을 만들 수 있는지 확인
    if (y-1 >= 0 and not check[westIdx]) and (x+1 < N and not check[southIdx]):
        check[idx] = True
        check[westIdx] = True
        check[southIdx] = True
        for i in range(idx+1, N*M+1):
            solve(i, sum + (board[x][y]*2 + board[x][y-1] + board[x+1][y]))
        check[westIdx] = False
        check[southIdx] = False
        check[idx] = False

    #   ㅁ
    # ㅁㅁ 형태의 부메랑을 만들 수 있는지 확인
    if (y-1 >= 0 and not check[westIdx]) and (x-1 >= 0 and not check[northIdx]):
        check[idx] = True
        check[westIdx] = True
        check[northIdx] = True
        for i in range(idx+1, N*M+1):
            solve(i, sum + (board[x][y]*2 + board[x][y-1] + board[x-1][y]))
        check[westIdx] = False
        check[northIdx] = False
        check[idx] = False

    # ㅁ
    # ㅁㅁ 형태의 부메랑을 만들 수 있는지 확인
    if (x-1 >= 0 and not check[northIdx]) and (y+1 < M and not check[eastIdx]):
        check[idx] = True
        check[northIdx] = True
        check[eastIdx] = True
        for i in range(idx+1, N*M+1):
            solve(i, sum + (board[x][y]*2 + board[x-1][y] + board[x][y+1]))
        check[northIdx] = False
        check[eastIdx] = False
        check[idx] = False


if __name__ == '__main__':
    N, M = map(int, input().split())
    board = []
    check = [False for _ in range(N*M)]
    res = 0

    for _ in range(N):
        board.append(list(map(int, input().split())))

    for i in range(N*M):
        solve(i, 0)

    print(res)