[백준] 테트로미노

문제

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

TC

각 점에 대해 DFS 수행
n과 m이 최대 500이고, 회전한 테트로미노는 19가지의 경우이므로
O(500 x 500 x 19) 정도의 시간이 소요된다.

Idea

4방향으로 회전된 테트로미노들을 잘 보면 'ㅗ'모양의 테트로미노를 제외한 다른 테트로미노들은 현재 위치에서 dfs를 최대 4의 깊이만큼 탐색을 하면, 모두 구해질 수 있다는 사실을 알 수 있다.

그래서, 깊이 4만큼의 dfs를 n * m 만큼 돌린 후, 'ㅗ' 모양의 도형만 직접 따로 구해주는 방식으로 풀면 좀 더 쉽게 풀 수 있다.

code (Python)

def dfs(x, y, dsum, cnt):
    global result

    # 4개의 칸을 다 채웠으면 최댓값 찾기
    if cnt == 4:
        result = max(result, dsum)
        return

    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]

        # 범위 내이고 방문한 적이 없는 위치라면
        if 0 <= nx < n and 0 <= ny < m and not visited[nx][ny]:
            visited[nx][ny] = True
            dfs(nx, ny, dsum + graph[nx][ny], cnt + 1)
            visited[nx][ny] = False

# ㅏ, ㅓ, ㅗ, ㅜ 체크 함수
def exce(x, y):
    global result

    for i in range(4):
        # 4가지 모음의 기준점
        temp = graph[x][y]
        for j in range(3):
            # 012,123,230,301 세방향만 체크
            k = (i+j) % 4
            nx = x + dx[k]
            ny = y + dy[k]

            # 범위 내의 위치라면
            if 0 <= nx < n and 0 <= ny < m:
                temp += graph[nx][ny]

        result = max(result, temp)

# 입력 조건
n, m = map(int, input().split())
graph = [list(map(int, input().split())) for _ in range(n)]
# 방문 여부 체크
visited = [[False for _ in range(m)] for _ in range(n)]

dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]

result = 0
for i in range(n):
    for j in range(m):
        # 방문한 적 없는 위치라면 방문해보기
        if not visited[i][j]:
            visited[i][j] = True
            dfs(i, j, graph[i][j], 1)
            visited[i][j] = False

            # ㅏ, ㅓ, ㅗ, ㅜ 중 최댓값 찾기 위한 함수
            exce(i, j)

print(result)

self code review

'ㅗ' 모양의 테트로미노 (회전하면 'ㅏ', 'ㅓ', 'ㅜ')를 어떻게 구해야 할 지 고민이 많았다.
다른 테트로미노는 상하좌우로 움직이면 방문할 수 있었지만, 이 테트로미노는 하나의 중심을 기준으로 세 방향의 날개(?)들이 있었기 때문에 다른 방법이 필요했다.

따로 함수를 구현해야될 필요성을 느끼긴 했지만, 저 3개의 방향들을 어떻게 구해야 될 지...아이디어가 떠오르지 않아 헤매었던 문제이다.

다른 분 풀이를 보며 방법을 알았으니, 나중에 다시 한 번 풀어봐야겠다.

reference

다른 분들의 풀이를 보다가 좋은 블로그를 발견해서 링크를 걸어두려고 한다.

https://cijbest.tistory.com/87