[백준] 14500 테트로미노 (파이썬)

문제 출처: 백준 온라인 저지

14500번: 테트로미노

 

문제 설명

🔎 폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다.
- 정사각형은 서로 겹치면 안 된다.
- 도형은 모두 연결되어 있어야 한다.
- 정사각형의 변끼리 연결되어 있어야 한다. 즉, 꼭짓점과 꼭짓점만 맞닿아 있으면 안 된다.
정사각형 4개를 이어 붙인 폴리오미노는 테트로미노라고 하며, 다음과 같은 5가지가 있다.

출처: 백준 온라인 저지

아름이는 크기가 N×M인 종이 위에 테트로미노 하나를 놓으려고 한다.
종이는 1×1 크기의 칸으로 나누어져 있으며, 각각의 칸에는 정수가 하나 쓰여 있다.
테트로미노 하나를 적절히 놓아서 테트로미노가 놓인 칸에 쓰여 있는 수들의 합을 최대로 하는 프로그램을 작성하시오.

(테트로미노는 반드시 한 정사각형이 정확히 하나의 칸을 포함하도록 놓아야 하며, 회전이나 대칭을 시켜도 된다.)

---

처음에는 문제를 잘못 읽어서 저것들을 하나씩 다 놔야하는 줄 알고, 이렇게 어려운 문제가 기초 강의 문제라고..? 생각했다.

 

물론 문제를 푸는 것이 쉽지는 않았으나, 다행히 저 도형들 중 하나만 놓아도 돼서 비교적 많이 쉬워졌다.

 

배열 원소 값은 상관없었고, N과 M은 500이라는 비교적 작은 숫자여서 완전 완전 탐색으로 진행했다.

product를 이용해서 갈 수 있는 모든 방향에 대해 구했고, (product의 길이는 64였다.) product를 탐색하면서 가장 큰 값을 구하는 그런 방법이었다.

 

product배열로는 'ㅗ, ㅜ, ㅓ, ㅏ' 모양을 구현할 수 없었기에 해당 방식을 구현하는 함수를 또 작성해준 후에야 정답에 접근할 수 있었다.

 

<틀린 코드 보기>

import sys
from itertools import product
inp = sys.stdin.readline


def place(x, y):
    val = 0
    for c in case:
        temp = paper[x][y]
        nx, ny = x, y
        visit = set()
        visit.add((nx, ny))
        flag = False
        
        for dx, dy in c:
            nx = nx+dx
            ny = ny+dy
            if (nx, ny) in visit:
                flag = True
                break
            if 0 <= nx < n and 0 <= ny < m:
                temp += paper[nx][ny]
                visit.add((nx, ny))
            else:
                flag = True
                break
                
        if not flag:
            val = max(val, temp)

    return val

def last_place(x, y):
    moves = [[[0, 1], [0, 1], [-1, -1]], [[0, 1], [0, 1], [1, -1]], [[1, 0], [1, 0], [-1, 1]], [[1, 0], [1, 0], [-1, -1]]]
    val = 0
    for move in moves:
        flag = False
        nx, ny = x, y
        temp = paper[nx][ny]

        for dx, dy in move:
            nx, ny = nx+dx, ny+dy

            if 0 <= nx < n and 0 <= ny < m:
                temp += paper[nx][ny]
            else:
                flag = True

        if not flag:
            val = max(temp, val)

    return val


n, m = map(int, inp().split())
paper = [list(map(int, inp().split())) for _ in range(n)]
answer = 0
case = list(product([[1, 0],[-1, 0],[0, 1],[0, -1]], repeat=3))

for i in range(n):
    for j in range(m):
        answer = max(answer, place(i, j))
        answer = max(answer, last_place(i, j))

print(answer)

작성한 코드는 python3로는 통과하지 못했고, pypy3로는 통과했다. 실행시간과 메모리 사용량 모두 불만족스러웠다. Python3로도 통과하지 못했기 때문에 프로그래머스였다면 정확성만 통과한 코드라 취급하고 다른 방법을 모색했다.

 

진짜 정답 코드에서는 원리는 같지만 dfs를 활용했고, max값을 이용해 불필요한 계산을 하지 않았다는 점이 내 코드와 차이가 있었다.

 

<정답 코드>

def dfs(x, y, depth, cur):
    global answer

    if cur + max_val*(4-depth) <= answer:
        return

    if depth == 4:
        answer = max(answer, cur)
        return

    for dx, dy in moves:
        nx, ny = x + dx, y + dy

        if 0 <= nx < n and 0 <= ny < m and not visit[nx][ny]:
      		# 'ㅗㅜㅓㅏ' 구현
            if depth == 2:
                visit[nx][ny] = True
                dfs(x, y, depth+1, cur + paper[nx][ny])
                visit[nx][ny] = False

            visit[nx][ny] = True
            dfs(nx, ny, depth+1, cur + paper[nx][ny])
            visit[nx][ny] = False



n, m = map(int, input().split())
paper = [list(map(int, input().split())) for _ in range(n)]
answer = 0

visit = [[False]*m for _ in range(n)]
moves = [(-1, 0), (1, 0), (0, -1), (0, 1)]
max_val = max(map(max, paper))

for i in range(n):
    for j in range(m):
        visit[i][j] = True
        dfs(i, j, 1, paper[i][j])
        visit[i][j] = False

print(answer)

접근은 아래와 같다.

1. 모든 좌표에서 dfs를 실행한다.
2. 갔다가 다시 되돌아오는 경우도 있기 때문에 visit을 통해서 방지한다.
3. 모든 도형은 총 4개의 작은 사각형으로 이루어져 있기 때문에 탈출 조건은 아래와 같다.
   1. 현재 값에서 가장 큰 값을 가능한 많이 더해도 현재 answer 값 보다 작으면 return한다.
   2. 깊이(depth)가 4가 되면 answer을 업데이트한 후 탈출한다.
4. 'ㅗ, ㅜ, ㅓ, ㅏ'는 무조건 갔던 길을 한번 되돌아와야하기 때문에 분기점인 depth=2에서 현재 위치에 대한 재귀를 또 한번 수행한다.
5. 한번의 도형 탐색이 끝나면 방문했던 경로들을 초기화 시켜준다.

일반적으로 재귀 함수는 실행 속도가 느리지만, 탈출 조건이 명확하고 depth가 4밖에 안되기 때문에 빠르게 돌아갔다.

실행속도가 10배 넘게 빨라졌고 메모리 소비량도 1/3가량으로 줄었다.

 

혹시나 해서 내가 작성했던 'ㅗ, ㅜ, ㅓ, ㅏ'를 확인하는 함수로 진행했을 때는 어떤가 확인해봤더니

그냥 중간정도로 나왔다. Python3로 통과되는 것에 의의를 두기로 했다.

 

탈출 조건을 잘 설정하는 것만으로도 시간을 많이 단축할 수 있다는 사실이 좀 놀라웠고, dfs는 이제 학을 땠다라고 생각했지만 여전히 모르는 것 투성이었다.