[Backtracking] 테트리스 블럭 안의 합 최대화 하기 - 삼성전자

문제

테트리스 블럭 안의 합 최대화 하기

n x m크기의 이차원 영역의 각 위치에 자연수 하나가 적혀있습니다. 이 때 아래의 그림에 주어진 다섯가지 종류의 테트리스 블럭 중 한 개를 적당히 올려놓아 블럭이 놓인 칸 안에 적힌 수의 합이 최대가 될 때의 결과를 출력하는 코드를 작성해보세요. 단, 주어진 테트리스 블럭은 자유롭게 회전하거나 뒤집을 수 있습니다.

입력

첫번째 줄에는 정수 n과 m이 공백을 사이에 두고 주어집니다.

두번째 줄부터 (n+1)번째 줄까지는 각 행에 해당하는 정수가 공백을 사이에 두고 주어집니다.

제한 조건

• 4 ≤ n, m ≤ 200
• 1 ≤ 자연수 ≤ 1,000

출력

테트리스 블럭 안에 적힌 숫자합의 최대값을 출력합니다.

입력 예제

예제 1

4 5
6 5 4 3 1
3 4 4 14 1
6 1 3 15 5
3 5 1 16 20

65

예제 설명입니다. 아래와 같이 블럭을 놓았을 때 합이 최대가 됩니다.

제한

• Time Limit: 4000 ms
• Memory Limit: 80 MiB

발상

블럭 다섯 종류를 회전하고 뒤집는다는 조건을 “격자에서 서로 붙어 있는 네 칸을 고른다” 로 바꿔 읽었습니다. 다섯 종류는 모두 네 칸짜리 도형, 즉 테트로미노이고 회전과 뒤집기를 다 펴면 서로 다른 모양이 19가지입니다. 이 19가지를 좌표로 적어 두고 전부 대보는 방법도 있지만, 붙어 있는 네 칸을 직접 이어 붙이면 모양 목록을 손으로 만들지 않아도 됩니다.

그래서 한 칸에서 시작해 이웃 칸으로 걸어가며 네 칸을 모으는 DFS로 갔습니다. 지나온 칸은 visited 로 막고, 돌아 나올 때 다시 풀어 주는 백트래킹입니다.

여기서 한 번 걸렸습니다. 걸어서 모으면 한 줄로 이어지는 모양만 나옵니다. I, O, L, J, S, Z는 한 붓 그리기가 되지만 T는 가운데 칸에서 세 방향으로 갈라져서 걸어서는 만들어지지 않습니다.

그래서 T만 따로 세기로 했습니다. 칸 하나를 가운데로 잡고 상하좌우 네 칸을 더해 십자 다섯 칸을 만든 다음, 팔 하나를 빼면 T가 된다고 봤습니다.

이 방법이 틀렸습니다. 가장자리 칸은 이웃이 셋뿐이라 십자를 만들어도 다섯 칸이 아니라 이미 네 칸입니다. 그 상태가 곧 T인데 거기서 팔을 하나 더 빼니 세 칸이 되어, 정작 답인 T를 세지 못했습니다.

아래 입력에서 걸렸습니다. 답은 8인데 7이 나왔습니다.

4 4
2 1 1 1
2 2 1 1
2 1 1 1
1 1 1 1

왼쪽 세로 세 칸 2, 2, 2에 오른쪽 2가 붙은 T가 8입니다. 이 T의 가운데 칸은 1행 0열이고, 왼쪽이 격자 밖이라 이웃이 셋입니다. 십자를 만들면 그대로 8인데, 여기서 팔 하나를 빼서 6으로 만들어 버렸습니다.

T를 따로 처리하는 것이 문제였습니다. 격자 안쪽이냐 가장자리냐에 따라 십자의 칸 수가 달라지는데, 그 차이를 팔 빼기 한 줄로 덮으려 한 것입니다.

그래서 따로 처리하지 않고 DFS 안으로 넣었습니다. 네 칸 중 두 칸을 모은 시점에 이웃 하나를 세고도 제자리에 머무르는 분기를 하나 더 팠습니다. 그러면 다음 걸음도 같은 칸에서 나가기 때문에 한 칸이 세 방향으로 뻗는 모양이 만들어집니다. 십자를 만들 일이 없으니 가장자리인지 따질 일도 없어집니다.

n과 m이 200 이하라 칸은 최대 4만 개입니다. 시작 칸마다 도는 탐색이 깊이 4로 고정이면 전체가 칸 수에 상수를 곱한 정도라, 4초 제한 안에 듭니다.

풀이

제출한 코드입니다.

N, M = list(map(int,input().split()))
ans = 0
board = [list(map(int,input().split())) for n in range(N)]
visited = [ [ 0 for m in range(M)] for n in range(N)]
dx = [1,-1,0,0]
dy = [0,0,1,-1]

def dfs(x, y, cnt, sum):
    global ans
    if (cnt == 4):
        ans = max(ans, sum)
        return sum

    for dir in range(4):
        nx, ny = x+dx[dir], y+dy[dir]
        if ( 0 <= nx < N and 0 <= ny < M and visited[nx][ny] == 0):
            visited[nx][ny] = 1
            if ( cnt == 2):
                dfs(x,y, cnt+1, sum+board[nx][ny])
            dfs(nx,ny, cnt+1, sum + board[nx][ny])
            visited[nx][ny] = 0

for n in range(N):
    for m in range(M):
        visited[n][m] = 1
        dfs(n,m,0,0)
        visited[n][m] = 0

print(ans)

cnt == 2 일 때의 분기가 T를 만드는 자리입니다. 위쪽 dfs(x,y, ...) 는 board[nx][ny] 를 합에 더하면서도 좌표는 x, y 그대로 넘깁니다. 다음 걸음이 다시 x, y 에서 나가므로 그 칸에 두 번째 가지가 붙습니다. 아래쪽 dfs(nx,ny, ...) 는 원래대로 옮겨 가는 걸음입니다.

시작 칸은 합에 들어가지 않습니다. dfs(n,m,0,0) 이라 sum 이 0에서 출발하고, 그 뒤 네 번의 걸음에서 더해진 칸만 세어집니다. 시작 칸은 visited 로 막혀 자리만 차지하고, 실제로 답이 되는 네 칸은 그다음부터 밟는 칸들입니다.

예제 입력을 넣은 결과입니다.

4 5
6 5 4 3 1
3 4 4 14 1
6 1 3 15 5
3 5 1 16 20

65

복잡도

구분	값
입력 크기	4 <= n, m <= 200
시간	O(nm)
공간	O(nm)

시간이 O(nm)인 이유는 시작 칸이 nm개이고, 시작 칸 하나에서 도는 탐색의 크기가 입력과 무관하게 묶이기 때문입니다. 깊이가 4로 고정이고 각 단계에서 방향이 넷뿐이라 재귀 호출 수에 상한이 있습니다. 사방이 뚫린 안쪽 칸 하나로 재어 보니 dfs 호출이 261회, cnt == 4 에 도달한 것이 172회였습니다. 즉 nm에 상수 261을 곱한 정도입니다.

공간이 O(nm)인 이유는 board 와 visited 가 각각 nm칸을 쓰기 때문입니다. 재귀 깊이는 4로 고정이라 호출 스택은 상수입니다.

이 복잡도로 제한 안에 드는 근거입니다. n = m = 200이면 칸이 4만 개이고 261을 곱하면 약 1044만 번입니다. 값을 1부터 1,000 사이에서 무작위로 채운 200 x 200 입력을 만들어 돌려 보니 파이썬 3.14에서 2.47초가 걸렸습니다. 시간 제한 4000ms 안에 듭니다. 여유가 크지 않아서 cnt == 2 분기를 더 늘리거나 안쪽에서 리스트를 새로 만들면 넘어갈 수 있습니다.

정리

막힌 곳은 T를 예외로 뺀 것이었습니다. 예외를 만들면 그 예외가 격자 가장자리에서 또 갈라집니다. 걸어서 안 나오는 모양이 있으면 걷는 방식 자체에 분기를 더하는 쪽이, 그 모양만 따로 세는 쪽보다 경우를 덜 만듭니다.

다른 풀이는 처음에 접었던 방법입니다. 테트로미노 19가지를 좌표 목록으로 적어 두고 모든 위치에 대보는 것입니다. 차수는 O(19nm)로 같고 코드도 더 짧습니다. 대신 19가지를 손으로 적다가 빠뜨리기 쉽습니다.

이 19가지 완전 탐색을 따로 짜서 위 코드와 답을 맞춰 보았습니다. 4 x 4부터 7 x 7까지 무작위 격자 300개에서 두 결과가 모두 같았습니다.