[BOJ 14500] 테트로미노(Python)

문제

테트로미노

문제 해설

ㅗ,ㅜ,ㅓ,ㅏ를 제외한 모든 도형은 회전과 대칭을 포함하여 DFS로 depth가 4인 모든 경우를 탐색하면 해결됩니다.

ㅗ,ㅜ,ㅓ,ㅏ는 따로 핸들링해줘도 되고 depth가 3일때 ㄴ,ㄱ,ㅡ,ㅣ 모양이 됩니다. 여기에서 바로 이전에 방문한 칸에 한칸 더가면 ㅗ,ㅜ,ㅓ,ㅏ모양을 처리할 수 있습니다. ㅡ,ㅣ 인 경우가 있기 때문에 한칸 더 갔을 경우 방문하지 않은 곳이어야 합니다.

풀이 코드

import sys

input = sys.stdin.readline
n, m = map(int, input().split())
answer = 0
visited = [[False] * m for _ in range(n)]
graph = []

for _ in range(n):
    graph.append(list(map(int, input().split())))


def dfs(depth, x, y, tot):
    global n, m, answer
    dx = -1, 0, 1, 0
    dy = 0, 1, 0, -1

    if depth == 4:
        answer = max(answer, tot)
        return
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        xx = nx + dx[i]
        yy = ny + dy[i]
        # 길이가 3이고, 방금 지나온 곳을 한번 더 지나 그곳이 방문하지 않은 곳이면
        # ㅗ,ㅓ,ㅏ,ㅜ 이다.
        if (
            depth == 3
            and 0 <= nx < n
            and 0 <= ny < m
            and visited[nx][ny]
            and 0 <= xx < n
            and 0 <= yy < m
            and not visited[xx][yy]
        ):
            dfs(depth + 1, xx, yy, tot + graph[xx][yy])
        # 범위 안에 있고 방문하지 않은곳만 탐색
        if 0 <= nx < n and 0 <= ny < m and not visited[nx][ny]:
            visited[nx][ny] = True
            dfs(depth + 1, nx, ny, tot + graph[nx][ny])
            visited[nx][ny] = False


# 한칸씩 확인하며 dfs
for i in range(n):
    for j in range(m):
        # ㅗ를 제외한 나머지 도형
        visited[i][j] = True
        dfs(1, i, j, graph[i][j])
        visited[i][j] = False
print(answer)