백준 14500번 : 테트로미노(python)

문제

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

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

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

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

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

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

입력

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

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

출력

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

예제 입력 1 복사

5 5
1 2 3 4 5
5 4 3 2 1
2 3 4 5 6
6 5 4 3 2
1 2 1 2 1

예제 출력 1 복사

19

예제 입력 2 복사

4 5
1 2 3 4 5
1 2 3 4 5
1 2 3 4 5
1 2 3 4 5

예제 출력 2 복사

20

예제 입력 3 복사

4 10
1 2 1 2 1 2 1 2 1 2
2 1 2 1 2 1 2 1 2 1
1 2 1 2 1 2 1 2 1 2
2 1 2 1 2 1 2 1 2 1

예제 출력 3 복사

7

코드

def dfs(x,y,end_x,end_y,cnt,sum):
    #'ㅗ'를 뺀 나머지 테트리스
    global max
    dx=[-1,0,1,0]
    dy=[0,-1,0,1]
    #이동범주
    if(cnt==3):
        #4번째 블록에 도달했을때
        sum+=arr[y][x]
        if(max<sum):
            max=sum
            return
        else:
            return
    for i in range(4):
        #다음 블록으로 이동
        if(0<=x+dx[i]<end_x and 0<=y+dy[i]<end_y):
            #블록이 범위를 벗어났는지 확인
            if(visit[y+dy[i]][x+dx[i]]==0):
                #블록이 이전에 방문했는지 안했는지 확인
                #방문 안했다면 다음 블록으로 이동
                visit[y][x]=1
                dfs(x+dx[i],y+dy[i],end_x,end_y,cnt+1,sum+arr[y][x])
                visit[y][x]=0

def dfs2(x,y,end_x,end_y):
    global max
    sum=0
    if(0<=x+2<end_x):
        #해당 블록에서 x축으로 2블록까지 갔을때 범위를 벗어나는지 확인
        for i in range(x,x+3):
            sum+=arr[y][i]
        if(0<=y+1<end_y):
            #y축으로 한블록 이동했을때 범위가 벗어나는지
            if(max<sum+arr[y+1][x+1]):
                #'ㅜ' 모양일때 max보다 크다면 max 업데이트
                max=sum+arr[y+1][x+1]        
        if(0<=y-1<end_y):
            #y축으로 한블록 이동했을때 범위가 벗어나는지
            if(max<sum+arr[y-1][x+1]):
                #'ㅗ'모양일때 max보다 크다면 max업데이트
                max=sum+arr[y-1][x+1]        
    sum=0
    if(0<=y+2<end_y):
        #해당 블록에서 y축으로 2블록까지 갔을때 범위를 벗어나는지 확인
        for i in range(y,y+3):
            sum+=arr[i][x]
        if(0<=x+1<end_x):
            #x축으로 한블록 이동했을때 범위가 벗어나는지
            if(max<sum+arr[y+1][x+1]):
                #'ㅏ' 모양일때 max보다 크다면 max 업데이트
                max=sum+arr[y+1][x+1]
        if(0<=x-1<end_x):
            #x축으로 한블록 이동했을때 범위가 벗어나는지
            if(max<sum+arr[y+1][x-1]):
                #'ㅓ' 모양일때 max보다 크다면 max 업데이트
                max=sum+arr[y+1][x-1]         
    
n,m=map(int,input().split())
arr=[]
visit=[[0 for i in range(m)] for j in range(n)] #방문확인리스트
max=0
cnt=0
sum=0
for i in range(n):
    arr.append(list(map(int,input().split())))
    #블록 리스트
    
for i in range(n):
    for j in range(m):
        dfs(j,i,m,n,cnt,sum)
        dfs2(j,i,m,n)
print(max)

코드설명

'ㅜ'모양의 테트리스를 뺀 나머지 테트리스들은 모두 한번에 갈수있는 연결된 모양의 테트리스 종류의 전부이다. 즉 dfs를 이용하면 모든 모양의 테트리스를 만들수 있다.

하지만, 'ㅜ' 모양은 dfs로 만들수 없기에 직접 같은모양이 나오는 경우를 코드로 따로 만들어주었다.

느낀점 및 배운점

처음에는 직접 모든 모양을 만드는것으로 문제를 풀려했지만, 코드가 너무 길어지고, 어느부분에서 잘못됬는지를 찾는것도 꽤 어려운 문제가 되었다. 때문에 서로 연결되어있는 모양일때는 일단 dfs 또는 bfs로 푸는것을 생각해보는것이 좋을것 같다.