백준 #18430 무기 공학

문제 설명

숫자가 쓰여있는 $m \times n$ 크기의 배열이 주어지고 칸을 ㄱ 자 모양을 뒤집거나 회전 시킨 아이들로 채웠을 때 덮어지는 수들의 최대합을 구하기

코드

import sys
input = sys.stdin.readline


def solve(r, c, value):
    global max_v

    if c == m:
        r += 1
        c = 0

    if r == n:
        if max_v < value:
            max_v = value
        return

    if not visited[r][c]:
        for k in range(4):
            if k == 0:
                nr, nc = r + 1, c - 1
            elif k == 1:
                nr, nc = r - 1, c - 1
            elif k == 2:
                nr, nc = r - 1, c + 1
            elif k == 3:
                nr, nc = r + 1, c + 1

            if 0 <= nr < n and 0 <= nc < m:
                if not visited[nr][c] and not visited[r][nc]:
                    visited[r][c] = True
                    visited[nr][c] = True
                    visited[r][nc] = True
                    solve(r, c + 1, value + 2 * arr[r][c] + arr[nr][c] + arr[r][nc])
                    visited[r][c] = False
                    visited[nr][c] = False
                    visited[r][nc] = False
    solve(r, c + 1, value)

    return


n, m = map(int, input().split())
arr = [list(map(int, input().split())) for _ in range(n)]
visited = [[False]* m for _ in range(n)]
max_v = 0
solve(0, 0, 0)
print(max_v)

풀이

아침 코딩스터디 때 다루었던 문제인데 모든 칸을 재귀적으로 탐색하는 방법을 처음 알았다! 열의 인덱스만 1씩 증가시켜주고 열의 인덱스 범위가 초과 했을 때 행 인덱스를 1 증가시켜주고 열 인덱스는 0으로 초기화 시켜준다. 이렇게하면 모든 칸에 대해서 탐색을 할 수 있다.