테트리스 블럭 안의 합 최대화 하기 (테트로미노)

문제 출처 : 코드트리_테트리스 블럭 안의 합 최대화 하기
티어 : 골드4
유형 : 시뮬레이션
출제 : 2017년 상반기 오전 1번
주의사항 : 일반적인 백트래킹으로는 풀리지 않음에 유의할 것!

---

문제가 참 짧죠? 풀 수 있는 방법이 매우 다양한 문제입니다. 저는 브루트포스로 두 번, 백트래킹으로 두 번 총 네 가지 방법으로 풀었지만 비트마스킹 등의 기술도 쓸 수 있는, 그때그때 배웠던 것들을 써먹기 좋은 문제입니다. 이번 풀이는 백트래킹을 이용하였습니다.

---

생각의 흐름

처음에는 일반적인 깊이 4짜리 백트래킹으로 구현하자고 마음먹었습니다. 그러면 현재 위치에서 네 방향의 빈 칸을 찾아 블럭이 확장하게 되고, 모든 블럭을 만들 수 있을거라 생각했기 때문입니다. 하지만 이런 형태로 백트래킹을 구현했더니 바로 틀리더라구요! 이유는 끝에서 다음 블럭을 찾는 특성 상, 가운데에서 툭 튀어나가는 T모양 블럭을 만들 수가 없었기 때문입니다.

 

그래서 저는 재귀함수의 인자로 좌표값이 아니라, 현재 블럭의 상태 그대로를 전달하는 방식으로 해결하자고 생각하고 풀이에 돌입했습니다. 해당 함수에 대한 설명은 아래 스킬에서 다루겠습니다.

 

스킬

앞서 재귀함수의 인자로 좌표값이 아니라 현재 블럭의 상태를 그대로 전달한다고 말씀드렸습니다. 그림으로 표현을 해보겠습니다.

왼쪽은 현재 내가 있는 상태에서 다음 블럭을 찾는 것이기 때문에 T자형을 만들 수가 없습니다. 그러려면 가운데 블럭에서 두번 펼쳐야하기 때문입니다. 반면 오른쪽은 현재 블럭들이 들어있는 리스트를 통해 그 주변 위치를 모두 탐방하고, 이로 다음 후보의 좌표를 정하게 됩니다. 그러면 가운데 블럭의 양쪽도 후보에 들어갈 수 있게 되므로 T자 블럭을 만들 수 있겠네요. 자, 그럼 해당 스킬을 가지고 풀이를 봐보도록 하겠습니다.

 

풀이

def getInput():
    # 입력받는 함수
    global n, m, graph
    n, m = map(int, input().split())
    graph = [list(map(int, input().split())) for _ in range(n)]


def dfs(level, llist, cnt):
    # 백트래킹 함수
    global maxx
    if level == 4:
        if cnt > maxx:
            maxx = cnt
        return

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

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

            if 0<=nx<n and 0<=ny<m and not (nx,ny) in llist:
                llist.append((nx,ny))
                dfs(level+1, llist, cnt + graph[nx][ny])
                llist.pop()

# ===== 실제 실행하는 부분 =====
def main():
    global maxx

    getInput()
    maxx = -10
    for i in range(n):
        for j in range(m):
            dfs(1,[(i,j)], graph[i][j])
    print(maxx)

main()

 

여담

코딩테스트에서 가장 중요한건 문제를 푸는 것입니다. 비록 풀 방법이 떠오르지 않는다 해도, 끈기를 가지고 어떻게든 풀어내는 것이 취업과 자신의 미래를 향한 이로운 길입니다. 아래에 쓴 코드는 제가 정말 처음으로 코딩에 입문했을 때, bfs고 dfs고 아무것도 모를 때 테트로미노를 풀어냈던 코드입니다. 또한, 제 네 가지 풀이들 중 가장 압도적인 실행속도를 자랑하는 풀이입니다. 저는 이 때 문제를 풀어낸 제 자신에 대한 뿌듯함을 느꼈고, 앞으로 이 끈기로 못풀어낼 문제는 없다고 생각하고 모든 문제에 임하게 되었습니다. 이걸 보고 여러분들도 용기를 가질 수 있었으면 좋겠습니다.

# 맨 처음 테트로미노 코드
n, m = map(int, input().split())
graph = [list(map(int, input().split())) for _ in range(n)]

def line1(x, y):  # 세로 0,0 ~ x-4,y-1
    a = graph[x][y] + graph[x+1][y] + graph[x+2][y] + graph[x+3][y]
    return a
def line2(x, y):  # 가로 0,0 ~ x-1,y-4
    a = graph[x][y] + graph[x][y+1] + graph[x][y+2] + graph[x][y+3]
    return a
def square(x, y):  # 네모 0,0 ~ x-2,y-2
    a = graph[x][y] + graph[x+1][y] + graph[x][y+1] + graph[x+1][y+1]
    return a
def L1(x, y):  # L모양 0,0 ~ x-3,y-2
    a = graph[x][y] + graph[x+1][y] + graph[x+2][y] + graph[x+2][y+1]
    return a
def L2(x, y):  # L좌우대칭 0,1 ~ x-3,y-1
    a = graph[x][y] + graph[x+1][y] + graph[x+2][y] + graph[x+2][y-1]
    return a
def L3(x, y):  # L상하대칭 0,0 ~ x-3,y-2
    a = graph[x][y] + graph[x][y+1] + graph[x+1][y] + graph[x+2][y]
    return a
def L4(x, y):  # L반전 0,0 ~ x-3,y-2
    a = graph[x][y] + graph[x][y+1] + graph[x+1][y+1] + graph[x+2][y+1]
    return a
def L5(x, y):  # 눕힌 L 0,0 ~ x-2,y-3
    a = graph[x][y] + graph[x+1][y] + graph[x+1][y+1] + graph[x+1][y+2]
    return a
def L6(x, y):  # 눕힌L좌우 0,2 ~ x-2,y-1
    a = graph[x][y] + graph[x+1][y] + graph[x+1][y-1] + graph[x+1][y-2]
    return a
def L7(x, y):  # 눕힌L상하 0,0 ~ x-2,y-3
    a = graph[x][y] + graph[x][y+1] + graph[x][y+2] + graph[x+1][y]
    return a
def L8(x, y):  # 눕힌L반전 0,0 ~ x-2,y-3
    a = graph[x][y] + graph[x][y+1] + graph[x][y+2] + graph[x+1][y+2]
    return a
def S1(x, y):  # S모양 0,0 ~ x-3,y-2
    a = graph[x][y] + graph[x+1][y] + graph[x+1][y+1] + graph[x+2][y+1]
    return a
def S2(x, y):  # S좌우대칭 0,1 ~ x-3,y-1
    a = graph[x][y] + graph[x+1][y] + graph[x+1][y-1] + graph[x+2][y-1]
    return a
def S3(x, y):  # S모양눕힘 1,0 ~ x-1,y-3
    a = graph[x][y] + graph[x][y+1] + graph[x-1][y+1] + graph[x-1][y+2]
    return a
def S4(x, y):  # S눕힘좌우 0,0 ~ x-2,y-3
    a = graph[x][y] + graph[x][y+1] + graph[x+1][y+1] + graph[x+1][y+2]
    return a
def F1(x, y):  # 뻐큐모양 1,0 ~ x-1,y-3
    a = graph[x][y] + graph[x][y+1] + graph[x][y+2] + graph[x-1][y+1]
    return a
def F2(x, y):  # 뻐큐 상하 0,0 ~ x-2,y-3
    a = graph[x][y] + graph[x][y+1] + graph[x][y+2] + graph[x+1][y+1]
    return a
def F3(x, y):  # 뻐큐 F모양 0,0 ~ x-3,y-2
    a = graph[x][y] + graph[x+1][y] + graph[x+2][y] + graph[x+1][y+1]
    return a
def F4(x, y):  # 뻐큐 F좌우 0,1 ~ x-3,y-1
    a = graph[x][y] + graph[x+1][y] + graph[x+2][y] + graph[x+1][y-1]
    return a


maxx = -1000

for i in range(n-3):
    for j in range(m):
        if line1(i,j)>maxx:
            maxx = line1(i,j)

for i in range(n):
    for j in range(m-3):
        if line2(i,j)>maxx:
            maxx = line2(i,j)

for i in range(n-1):
    for j in range(m-1):
        if square(i,j)>maxx:
            maxx = square(i,j)

for i in range(n-2):
    for j in range(m-1):
        if L1(i,j)>maxx:
            maxx = L1(i,j)

for i in range(n-2):
    for j in range(1,m):
        if L2(i,j)>maxx:
            maxx = L2(i,j)

for i in range(n-2):
    for j in range(m-1):
        if L3(i,j)>maxx:
            maxx = L3(i,j)

for i in range(n-2):
    for j in range(m-1):
        if L4(i,j)>maxx:
            maxx = L4(i,j)

for i in range(n-1):
    for j in range(m-2):
        if L5(i,j)>maxx:
            maxx = L5(i,j)

for i in range(n-1):
    for j in range(2,m):
        if L6(i,j)>maxx:
            maxx = L6(i,j)

for i in range(n-1):
    for j in range(m-2):
        if L7(i,j)>maxx:
            maxx = L7(i,j)

for i in range(n-1):
    for j in range(m-2):
        if L8(i,j)>maxx:
            maxx = L8(i,j)

for i in range(n-2):
    for j in range(m-1):
        if S1(i,j)>maxx:
            maxx = S1(i,j)

for i in range(n-2):
    for j in range(1,m):
        if S2(i,j)>maxx:
            maxx = S2(i,j)

for i in range(1,n):
    for j in range(m-2):
        if S3(i,j)>maxx:
            maxx = S3(i,j)

for i in range(n-1):
    for j in range(m-2):
        if S4(i,j)>maxx:
            maxx = S4(i,j)

for i in range(1,n):
    for j in range(m-2):
        if F1(i,j)>maxx:
            maxx = F1(i,j)

for i in range(n-1):
    for j in range(m-2):
        if F2(i,j)>maxx:
            maxx = F2(i,j)

for i in range(n-2):
    for j in range(m-1):
        if F3(i,j)>maxx:
            maxx = F3(i,j)

for i in range(n-2):
    for j in range(1,m):
        if F4(i,j)>maxx:
            maxx = F4(i,j)

print(maxx)