[백준] 무기공학

https://www.acmicpc.net/status?from_problem=1&problem_id=18430 

채점 현황

1. 문제 이해

N X M 크기의 직사각형에 강도를 의미하는 수가 적혀있습니다. 'ㄱ'모양으로 직사각형 내에서 선택할 수 있는데 

노란 부분에 해당하는 곳은 강도의 영향을 2배로 받는다고 할 때 부메랑들의 강도의 합의 최대값을 구하는 문제입니다.

2. 문제 접근

첫번째 접근: 백트래킹

N, M <= 5로 사이즈가 크지 않아서 백트래킹으로 접근해야겠다고 생각했습니다. 각각의 위치에서 부메랑을 직접 만들어보고 만약 이미 선택된 위치거나 범위를 넘어가면 선택하지 않는 방법을 사용하였습니다.

 

3. 풀이

import sys

sys.stdin = open("input.txt", "r")
input = sys.stdin.readline

n, m = tuple(map(int, input().split()))

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


dys = [(0, 0, 1), (0, 0, -1), (-1, 0, 0), (0, 0, 1)]
dxs = [(-1, 0, 0), (-1, 0, 0), (0, 0, 1), (0, 1, 0)]

visited = [
    [False] * m
    for _ in range(n)
]

def inRange(y, x):
    return 0 <= x < m and 0 <= y < n


ans = 0

def dfs(idx, val):
    global ans

    ans = max(ans, val)

    if idx == n * m:
        return

    y = idx // m
    x = idx % m

    if visited[y][x]:
        dfs(idx + 1, val)
        return

    for dy, dx in zip(dys, dxs):
        flag = False
        for i in range(3):
            ny = y + dy[i]
            nx = x + dx[i]

            # 방문했거나 범위를 넘어가면 부메랑을 만들 수 없다.
            if not inRange(ny, nx) or visited[ny][nx]:
                flag = True
                continue

        if flag:
            continue

        sum_of_val = 0
        for i in range(3):
            ny = y + dy[i]
            nx = x + dx[i]

            sum_of_val += board[ny][nx]

            visited[ny][nx] = True

        sum_of_val += board[y][x]

        dfs(idx + 1, val + sum_of_val)

        for i in range(3):
            ny = y + dy[i]
            nx = x + dx[i]

            visited[ny][nx] = False

    dfs(idx + 1, val)

dfs(0, 0)

print(ans)