오늘의 알고리즘 boj-14500

문제

폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다.

• 정사각형은 서로 겹치면 안 된다.
• 도형은 모두 연결되어 있어야 한다.
• 정사각형의 변끼리 연결되어 있어야 한다. 즉, 꼭짓점과 꼭짓점만 맞닿아 있으면 안 된다.
  정사각형 4개를 이어 붙인 폴리오미노는 테트로미노라고 하며, 다음과 같은 5가지가 있다.
  
  아름이는 크기가 N×M인 종이 위에 테트로미노 하나를 놓으려고 한다. 종이는 1×1 크기의 칸으로 나누어져 있으며, 각각의 칸에는 정수가 하나 쓰여 있다.
  테트로미노 하나를 적절히 놓아서 테트로미노가 놓인 칸에 쓰여 있는 수들의 합을 최대로 하는 프로그램을 작성하시오.
  테트로미노는 반드시 한 정사각형이 정확히 하나의 칸을 포함하도록 놓아야 하며, 회전이나 대칭을 시켜도 된다.

풀이

문제를 자세히 읽어보면 알 수 있듯이 정사각형이 4개 연결된 모든 값들을 찾으면 되는 문제이다. 4개의 상하좌우 연결이라고 하면 자연스럽게 dfs, bfs를 떠올릴 수 있고 4개의 연결된 폴리오미노를 구해야하기 때문에 depth를 통해 백트래킹으로 값을 구하면 되겠다고 생각했다.

백트래킹으로 코드를 제출하니 틀렸고 원인이 무엇인지 생각해보니 다른 테트로미노는 dfs를 따라가면 그릴 수 있지만 그림에서 ㅜ모양의 테트로미노는 그대로 따라가다보면 그릴 수 가 없다는 사실을 알게 되었다.

그래서 ㅜ 모양의 테트로미노를 4방향으로 돌려 각각 검사를 한다던가(시간초과) 검사횟수를 줄이기 위해 조건을 걸어 그 조건을 통과한 코드만 가능한 방향으로 돌린다던가(시간초과) 여러 방면으로 시도를 해보았지만 계속해서 시간초과가 나왔다.

그러다 가만히 보니 재귀 내부에서 해결할 수 있는 방법을 찾아야 시간초과를 피할 수 있겠다는 생각이 들었다.

일일히 손으로 ㅜ 모양을 그려가면서 고민해보니 depth가 1일때 다시 전 row, col 값으로 돌아가면 저 튀어나온 부분을 합으로 더하면서도 다른 연결된 부분에 대한 검사도 할 수 있으리라고 생각했다.

솔직히 방법을 알았어도 어떻게 해야할지 감이 잡히지 않아서 하나씩 출력을 찍어보며 해결했다. visited에 다음 이동값을 true로 바꿔주고 더하고 있는 cur_sum에는 다음 이동할 장소에 있는 값을 넣어주고 dfs의 실행을 이전으로 되돌리면 꼭짓점을 포함하면서 다시 row, col에 대한 4방향 검사를 실행하기 때문에 ㅜ 모양에 대한 검사를 할 수 있다.

import sys
input = sys.stdin.readline

N, M = map(int, input().split())
graph = [list(map(int, input().split())) for _ in range(N)]
visited = [[False] * M for _ in range(N)]
directions = [[0, -1], [-1, 0], [0, 1], [1, 0]]
answer = 0

def update_answer_to_max_value(depth, row, col, cur_sum):
    global answer
    if depth == 3:
        answer = max(answer, cur_sum)
        return
    
    for direction in directions:
        next_row = row + direction[0]
        next_col = col + direction[1]
        
        if next_row < 0 or next_row >= N or next_col < 0 or next_col >= M: continue
        
        if visited[next_row][next_col]: continue

        if depth == 1:
            visited[next_row][next_col] = True
            update_answer_to_max_value(depth+1, row, col, cur_sum + graph[next_row][next_col])
            visited[next_row][next_col] = False

        visited[next_row][next_col] = True
        update_answer_to_max_value(depth+1, next_row, next_col, cur_sum +graph[next_row][next_col])
        visited[next_row][next_col] = False

for i in range(N):
    for j in range(M):
        visited[i][j] = True
        update_answer_to_max_value(0, i, j, graph[i][j])
        visited[i][j] = False
print(answer)