[코딩 테스트 연습(파이썬/Python)] 백준 14500번 _ 테트로미노

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

14500번: 테트로미노

[문제]

폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다.

• 정사각형은 서로 겹치면 안 된다.
• 도형은 모두 연결되어 있어야 한다.
• 정사각형의 변끼리 연결되어 있어야 한다. 즉, 꼭짓점과 꼭짓점만 맞닿아 있으면 안 된다.

정사각형 4개를 이어 붙인 폴리오미노는 테트로미노라고 하며, 다음과 같은 5가지가 있다.

아름이는 크기가 N×M인 종이 위에 테트로미노 하나를 놓으려고 한다. 종이는 1×1 크기의 칸으로 나누어져 있으며, 각각의 칸에는 정수가 하나 쓰여 있다.

테트로미노 하나를 적절히 놓아서 테트로미노가 놓인 칸에 쓰여 있는 수들의 합을 최대로 하는 프로그램을 작성하시오.

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

 

[입력]

첫째 줄에 종이의 세로 크기 N과 가로 크기 M이 주어진다. (4 ≤ N, M ≤ 500)

둘째 줄부터 N개의 줄에 종이에 쓰여 있는 수가 주어진다. i번째 줄의 j번째 수는 위에서부터 i번째 칸, 왼쪽에서부터 j번째 칸에 쓰여 있는 수이다. 입력으로 주어지는 수는 1,000을 넘지 않는 자연수이다.

[출력]

첫째 줄에 테트로미노가 놓인 칸에 쓰인 수들의 합의 최댓값을 출력한다.

 

[아이디어]

1) 가능한 경우들을 모두 탐색해야한다.

2) 회전, 대칭을 포함해 만들 수 있는 테트로미노의 종류는 모두 19가지이다.

 

# 반례
# 4 4
# 4 10 2 2
# 3 6 1 6
# 4 2 1 3
# 2 1 6 2
n,m=map(int,input().split())
g = [list(map(int,input().split())) for _ in range(n)]

def f(x,g):
    i,j = x
    move = {'r':(0,1),'l':(0,-1),'u':(-1,0),'d':(1,0),'rr':(0,2),'rrr':(0,3),'dd':(2,0),'ddd':(3,0),
           'rd':(1,1),'rdd':(2,1),'ld':(1,-1),'lld':(1,-2),'ru':(-1,1),'ruu':(-2,1),'lu':(-1,-1),'luu':(-2,-1),
           'rru':(-1,2),'rrd':(1,2),'ldd':(2,-1)}
    tmp = [['r','rr','rrr'],['d','dd','ddd'],['r','d','rd'],['d','r','rr'],['r','rd','rdd'],['d','dd','rdd'],['d','ld','lld'],
          ['d','rd','rrd'],['r','ru','ruu'],['r','rr','rrd'],['r','d','dd'],['d','rd','rdd'],['r','ru','rru'],['d','ld','ldd'],
          ['r','rd','rrd'],['r','rr','rd'],['u','r','d'],['d','ld','rd'],['r','ru','rd']]
    cc = []
    for lst in tmp:
        c = []
        for x in lst:
            a,b = move[x]
            try:
                c.append(g[i+a][j+b])
            except:
                c.append(0)
        cc.append(sum(c))
    return max(cc)+g[i][j]
print(max([f((i,j),g) for i in range(n) for j in range(m)]))

이렇게 해결하긴 했지만, 매우 1차원적인 접근이고 dfs를 활용한 풀이도 가능하다고 한다. 사실 ㅗ,ㅏ 모양에 대한 예외 처리가 필요해서 떠올리고 구현하는데까지 시간은 비슷할 것 같다. 다만 나머지 모양에 대해 dfs로 접근했을 때 거리 4로 모든 케이스를 커버 가능하다는 아이디어는 좋은 접근인 것 같다. 결국 '4개 짜리' 도형을 만드는 것이 힌트였던 셈이다.

+ 위의 코드는 테스트 케이스가 약해서 통과됐었던 코드고 아래로 변경해야 맞다. i+a 혹은 j+b가 음수가 되는 경우를 고려해야한다.

n,m=map(int,input().split())
g = [list(map(int,input().split())) for _ in range(n)]
def f(x,g):
    i,j = x
    move = {'r':(0,1),'l':(0,-1),'u':(-1,0),'d':(1,0),'rr':(0,2),'rrr':(0,3),'dd':(2,0),'ddd':(3,0),
           'rd':(1,1),'rdd':(2,1),'ld':(1,-1),'lld':(1,-2),'ru':(-1,1),'ruu':(-2,1),'lu':(-1,-1),'luu':(-2,-1),
           'rru':(-1,2),'rrd':(1,2),'ldd':(2,-1)}
    tmp = [['r','rr','rrr'],['d','dd','ddd'],['r','d','rd'],['d','r','rr'],['r','rd','rdd'],['d','dd','rdd'],['d','ld','lld'],
          ['d','rd','rrd'],['r','ru','ruu'],['r','rr','rrd'],['r','d','dd'],['d','rd','rdd'],['r','ru','rru'],['d','ld','ldd'],
          ['r','rd','rrd'],['r','rr','rd'],['u','r','d'],['d','ld','rd'],['r','ru','rd']]
    cc = []
    for lst in tmp:
        c = []
        for x in lst:
            a,b = move[x]
            if 0<=i+a<n and 0<=j+b<m:
                c.append(g[i+a][j+b])
        cc.append(sum(c))
    return max(cc)+g[i][j]
print(max([f((i,j),g) for i in range(n) for j in range(m)]))