[BOJ] 14500번 - 테트로미노

---

문제설명

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

14500번: 테트로미노

사고과정

• 매우 어려운 문제였다.. 예전에 풀어본 카카오 자물쇠와 열쇠문제처럼 도형을 90도 회전이랑 맵을 모두 이동하면서 확인하나 해야 했다..근데 도형의 좌표값이 고정되어 있어서 역으로 보드 크기를 늘려서 보드를 움직이면서 도형의 좌표값과 일치하는 값들을 구해야 하나도 했다.. 하지만 끝내 구현하지 못했다..
• 그래서 풀이를 보니 정말로 노다가 방식으로 도형이 맵에 들어갈 수 있는 모든 경우의 수를 리스트에 담아서 하는 풀이도 있었지만 개인적으로 좀 더 알고리즘스럽게 풀고 싶어서 다른 풀이를 찾아보았다.
• 정답은 재귀함수를 사용한 DFS 를 이용하는 것이었다. 어떤 걸 깊이 탐색하냐? 바로 정사각형 한 칸이다. 즉, 주어진 도형 5가지는 정사각형 한칸을 상,하,좌,우로 재귀탐색했을 경우 나올 수 있는 모형들이다. 단, ㅗ,ㅏ,ㅜ,ㅓ와 같은 도형만 만들 수 없다. 그래서 ㅗ,ㅏ,ㅜ,ㅓ와 같은 도형을 DFS 함수 내에서 따로 처리해주도록 했다. 즉, 칸수가 2번까지 카운트된 다음 더 DFS 탐색을 수행하려 할 때, 위치는 이동하지 말고 합의 계산만 하는 것이다. 이는 아래의 소스코드 로직을 통해 이해하면 더 빠를 듯하다..
• 처음에 풀이를 이해하는데도 시간이 꽤걸려서 어제 풀이를 따라쳐보고 오늘 풀이를 2번 따라쳐보고 포스팅을 한다.. 아마 주기적으로 반복해서 풀어야할 듯 하다. 그런데 아직도 재귀함수의 형상이 머릿속에서 잘 안와닿는다.. 아직 갈 길이 먼 듯 싶다.
• 그리고 풀이를 보면서 새로운 문법을 알게되었다. 2차원 리스트의 전체 원소 중 최댓값을 구할 때는 아래와 같이 map과 max 함수를 활용할 수 있었다. 만약 board 리스트 앞에 unpacking(*) 기호를 붙여준다면 중첩된 리스트의 동일한 위치끼리 비교한 후 max 값을 내뱉어 준다.

풀이(스스로 못 푼 풀이)

import sys
input = sys.stdin.readline
n, m = map(int, input().split())
board = []
for _ in range(n):
    board.append(list(map(int, input().split())))
# 해당 칸 방문처리용 테이블
visited = [[False] * m for _ in range(n)]
max_val = max(map(max, board))
answer = 0

def dfs(k, value, r, c):
    global answer
    # 만약 칸(k) 개수가 4개면 도형 만든 거 끝남
    if k == 4:
        answer = max(answer, value)
        return
    # 만약 남은 칸 개수가 모두 보드 전체의 최댓값으로 다 이루어졌다 해도 현재 갱신값보다 작으면 리턴
    if value + (4 - k) * max_val <= answer:
        return
    # 테트로미노 도형 5가지 탐색하기 위한 이동 방향
    steps = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    for i, j in steps:
        nr, nc = r + i, c + j
        # 보드 안의 칸이라면
        if 0 <= nr < n and 0 <= nc < m:
            # 이동할 칸이 방문하지 않았다면
            if not visited[nr][nc]:
                visited[nr][nc] = True # 방문처리
                # 칸이 2개일 때 ㅗ,ㅏ,ㅜ,ㅓ 도형을 만들기 위해 위치는 고정
                if k == 2:
                    dfs(k+1, value + board[nr][nc], r, c)
                # 칸이 1개, 3개, 4개 상태면 위치 옮겨가면서 DFS 더 진행
                dfs(k+1, value + board[nr][nc], nr, nc)
                visited[nr][nc] = False # 이동한 칸 방문처리도 취소해야 다른 경우의 수 탐색할 때 영향 안 미침!


# 맵의 한 칸마다 모든 테트로미노 도형 경우의수 DFS 탐색
for i in range(n):
    for j in range(m):
        visited[i][j] = True
        dfs(1, board[i][j], i, j)
        visited[i][j] = False

print(answer)

 

위에서 언급했던 max, map을 활용한 2차원 리스트 최댓값 내뱉는 방법

 

a = [[1,2,100], [10,15,20]]
print(a)
print()
# 각 리스트의 최댓값을 내뱉음 -> 2개의 최댓값 반환
print(list(map(max, a)))
print()
# 각 리스트의 동일한 인덱스의 값끼리 비교해서 최댓값을 내뱉음 -> 3개의 최댓값 반환
print(list(map(max, *a)))