[Python/파이썬] 백준 18430번 무기 공학

18430번: 무기 공학

 

코드

n, m = map(int, input().split())
woods = [list(map(int, input().split())) for _ in range(n)]

boomerang = [[(0, -1), (1, 0)], [(0, -1), (-1, 0)],
             [(-1, 0), (0, 1)], [(0, 1), (1, 0)]]
visited = [[False]*m for _ in range(n)]
ans = 0


def bt(x, y, total):
    global ans
    if y >= m:
        x += 1
        y = 0
        if x >= n:
            ans = max(ans, total)
            return
    if not visited[x][y]:
        for a, b in boomerang:  # 4방향 부메랑 가능한지
            ax = x+a[0]
            ay = y+a[1]
            bx = x+b[0]
            by = y+b[1]
            if 0 <= ax < n and 0 <= ay < m and 0 <= bx < n and 0 <= by < m and not visited[ax][ay] and not visited[bx][by]:
                visited[ax][ay] = True
                visited[bx][by] = True
                visited[x][y] = True
                bt(x, y+1, total+woods[x][y] *
                    2+woods[ax][ay]+woods[bx][by])
                visited[ax][ay] = False
                visited[bx][by] = False
                visited[x][y] = False
    bt(x, y+1, total)   # 이 자리에 안 놓음


bt(0, 0, 0)
print(ans)

 

주어진 N×M 배열을 한 칸씩 차례대로 보면서 해당 칸을 중심으로 부메랑을 만든다/안 만든다 2가지 케이스로 나눠서 백트래킹을 진행하면 된다.

 

부메랑을 만들 때는 문제에 제시된 4방향을 모두 가능한지 살펴볼 것인데 양 날개가 N×M 범위를 벗어나지 않고 아직 다른 부메랑이 사용하지 않은 칸들이라면 그 방향으로 부메랑을 만들 수 있다.

 

부메랑을 만들지 않을 때는 현재 칸 (x, y)가 이미 사용되고 있는 경우도 포함이므로 if not visited[x][y] 조건문 밖에 만들어준다.