14500번 테트로미노

문제

https://www.acmicpc.net/problem/14500

1) bruteforce

가능한 모든 모양을 미리 저장해둔 뒤, 일일이 대입해보며 가장 큰 합을 구하는 방식이다.

풀다가 현타 온다는 특징이 있다.

코드

# 입력부
n, m = map(int, input().split())
board = [list(map(int, input().split())) for _ in range(n)]

def get_sum(cx, cy):
    # 모든 경우의 수
    sets = [
        [(0, 0), (0, 1), (0, 2), (0, 3)], [(0, 0), (1, 0), (2, 0), (3, 0)],
        [(0, 0), (0, 1), (1, 0), (1, 1)],
        [(2, 0), (0, 1), (1, 1), (2, 1)], [(0, 0), (1, 0), (2, 0), (2, 1)], [(0, 0), (0, 1), (1, 0), (2, 0)], [(0, 0), (0, 1), (1, 1), (2, 1)],
        [(0, 0), (1, 0), (1, 1), (1, 2)], [(1, 0), (1, 1), (1, 2), (0, 2)], [(0, 0), (0, 1), (0, 2), (1, 2)], [(0, 0), (0, 1), (0, 2), (1, 0)],
        [(0, 0), (1, 0), (1, 1), (2, 1)], [(1, 0), (2, 0), (0, 1), (1, 1)], [(0, 0), (0, 1), (1, 1), (1, 2)], [(0, 1), (0, 2), (1, 0), (1, 1)],
        [(0, 0), (0, 1), (0, 2), (1, 1)], [(0, 0), (1, 0), (2, 0), (1, 1)], [(1, 0), (1, 1), (1, 2), (0, 1)], [(1, 0), (0, 1), (1, 1), (2, 1)]
    ]

    cur_max_sum = 0
    for dirs in sets:
        pos = 0
        cur_sum = 0
        for dx, dy in dirs:
            if 0 <= cx + dx < n and 0 <= cy + dy < m:
                cur_sum += board[cx + dx][cy + dy]
                pos += 1
        if pos == 4:
            cur_max_sum = max(cur_sum, cur_max_sum)
    return cur_max_sum


max_sum = 0
for i in range(n):
    for j in range(m):
        cur_max = get_sum(i, j)
        if max_sum < cur_max:
            max_sum = cur_max

print(max_sum)

2) DFS

처음에는 어떻게 dfs로 푼다는건지 감이 안 잡혔는데, 그려보면 'ㅗ' 모양 제외하고 다 만들 수 있다 (회전, 뒤집기 상관없이)

코드

# 입력부
n, m = map(int, input().split())
board = [list(map(int, input().split())) for _ in range(n)]

# 'ㅗ' 제외 다른 도형들 (한붓그리기 가능)
def dfs(cx, cy, cnt, cur_sum):
    if cnt == 4:
        global max_sum2
        max_sum = max(max_sum, cur_sum)
        return

    for dx, dy in [(0, 1), (1, 0), (0, -1), (-1, 0)]:
        if 0 <= cx + dx < n and 0 <= cy + dy < m and not visited[cx + dx][cy + dy]:
            visited[cx + dx][cy + dy] = True
            cnt += 1
            cur_sum += board[cx + dx][cy + dy]
            dfs(cx + dx, cy + dy, cnt, cur_sum)
            cur_sum -= board[cx + dx][cy + dy]
            cnt -= 1
            visited[cx + dx][cy + dy] = False


max_sum = 0
visited = [[False] * m for _ in range(n)]
for i in range(n):
    for j in range(m):
        # 'ㅗ' 제외 dfs 수행
        visited[i][j] = True
        dfs(i, j, 1, board[i][j])
        visited[i][j] = False

        # 'ㅗ' 따로 처리
        for dirs in [[(0, 0), (0, 1), (0, 2), (1, 1)], [(0, 0), (1, 0), (2, 0), (1, 1)], [(1, 0), (1, 1), (1, 2), (0, 1)], [(1, 0), (0, 1), (1, 1), (2, 1)]]:
            tmp_sum, pos = 0, 0
            for di, dj in dirs:
                if 0 <= i + di < n and 0 <= j + dj < m:
                    tmp_sum += board[i + di][j + dj]
                    pos += 1
            if pos == 4:
                max_sum = max(tmp_sum, max_sum)

print(max_sum)

왠지 더 글로리 하도영씨가 한 말이 떠오르는 방식,,🫠 확실히 dfs가 미학적으로는 훨씬 보기 좋다 !
성능상으로는 첫번째 방식이 더 빠르다. 일반적으로 재귀함수를 활용하는 것보다 반복문 도는 게 더 빠른 것도 있지만, dfs는 중복해서 구하는 경우가 있어서 그런듯

👉 위에가 dfs, 아래가 bruteforce 방식 풀이