Python - [백준]14500-테트로미노

출처

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

문제

쉽게 말하면 테트리스에 나오는 도형들을 테트로미노라고 한다. 총 5가지의 종류가 있는데 이것들을 대칭시키거나 회전시켜도 된다.
맵을 하나 주고 그 안에 딱 하나의 테트로미노를 배치하여 그 안에 있는 숫자들의 합이 가장 큰 경우를 구해보는 문제이다.

접근 방법

어떤 모양으로 어디에 배치해야할지 찾는 문제이다. 딱 하나의 테트로미노만 배치해도 되기때문에 충분히 모든 경우를 찾아보아도 될 것 같다.
도형의 경우의 수도 너무 많지만, 'ㅗ' 모양의 블록을 제외하고는 상하좌우 남는 방면에 3개의 정사각형을 이어붙이다보면 만들 수 있다. 직접 그려보면 이해하기 쉬울 것이다. 나는 그 성질을 이용하여 dfs알고리즘을 적용하여 모든 도형을 만들어보고 탐색하도록 하였다.
'ㅗ'모양의 블럭은 따로 예외처리를 해주었다.

풀이

• 모든 좌표에 대해 탐색을 진행하는 for문 두개를 배치하고, dfs를 쓰는만큼 visited배열을 추가로 선언하여 탐색여부를 볼 수 있도록 하였다.
• 4개 방면에 대해 탐색을 진행하는데 맵 밖으로 나가거나 이미 방문했던 곳은 제외하였다.
• 재귀함수 호출을 사용하기때문에 종료조건또한 지정해주었다.

1. 만약 3칸 모두 이어붙였다면 기존의 값과 현재 얻은 값중 큰것을 저장한다
2. 다른 사람의 풀이를 참고하였는데, 만약 앞으로 내가 얻을 수 있는 점수의 기댓값이 현재 얻은 값보다 작다면, 더이상 탐색을 하지 않도록 하였다.

2번의 조건을 추가하였더니 시간복잡도에 걸리지 않았다.
'ㅗ'모양의 경우, 예외조건을 추가하여 cnt가 1일때 x, y에 대하여 즉, 자기자신의 dfs를 다시 호출하도록 하였다.

꽤 어려운 문제였다.

풀이코드

import sys
n, m = map(int, sys.stdin.readline().split())
arr = [list (map(int, sys.stdin.readline().split())) for _ in range(n)]
visited = [[0] * m for _ in range(n)]
max_val = max(map(max, arr))
res = 0
dx = [0, 1, 0, -1]
dy = [1, 0, -1, 0]

def is_possible(x, y):
    return 0 <= x < n and 0 <= y < m and visited[x][y] == 0

def dfs(x, y, cnt, tmp):
    global res
    if tmp + max_val*(4-cnt) <= res:
        return
    if cnt == 3:
        res = max(res, tmp)
        return
    else:
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if is_possible(nx,ny):
                if cnt == 1:
                    visited[nx][ny] = 1
                    dfs(x, y, cnt + 1, tmp + arr[nx][ny])
                    visited[nx][ny] = 0
                
                visited[nx][ny] = 1
                dfs(nx, ny, cnt + 1, tmp + arr[nx][ny])
                visited[nx][ny] = 0
            
    
    
for i in range(n):
    for j in range(m):
        visited[i][j] = 1
        dfs(i, j, 0, arr[i][j])
        visited[i][j] = 0

print(res)