[백준] 14500 - 테트로미노

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

14500번: 테트로미노

문제 한줄 이해

-5가지 테트리스에서 사용되는 모양들을 그래프에 위치 시켰을때 놓여진 부분들의 합이 제일 큰경우를 구하기

 

생각난 풀이

1번째 방법: 먼저 도형들의 규칙성을 찾으려고 노력했다. 각 점의 기준에서 상하좌우로 움직이면서 DFS로 탐색을 진행하면 원하는 모양을 만들 수 있는 것이다! 근데 ㅜ 이 모양은 DFS로 탐색을 진행한다고 해서 만들어 질 수 없는 모양이라 따로 처리를 해줘야한다고 생각했지만 좋은 방법이 떠오르지 않았다.

그래서 검색을 통해 힌트를 얻었는데 격자가 2개가 이어 붙여진 상태에서 다음 탐색을 할때 다음 좌표를 넘기는게 아닌 현재의 좌표를 넘겨주는 조건을 거는거다.

이유는 천천히 재귀를 따라가보면 알 수 있다.

2개가 이어진 상태에서 다음으로 탐색할 좌표를 True로 표시하고 현재 자리를 넘겨 준다면 total값에는 ㅡ 모양의 값이 담겨 있고

이때 탐색하지 않은 위 아래 를 탐색하면서 자연스럽게 ㅜ ㅗ ㅓ ㅏ등의 모양을 만들 수 있는 것이다.

import sys
n, m = map(int,sys.stdin.readline().split())

graph = []

for i in range(n):
    graph.append(list(map(int,sys.stdin.readline().split())))
            
def dfs(x,y,cnt,total):
    global result
    if cnt == 4:
        if result < total:
            result = total
        return
    dx = [0,0,1,-1]
    dy = [1,-1,0,0]
    
    for i in range(4):
        nextx = dx[i] + x
        nexty = dy[i] + y
        if nextx>= 0 and nexty>=0 and nextx<=n-1 and nexty<=m-1:
            if visited[nextx][nexty] == False:
                if cnt == 2:
                    visited[nextx][nexty] = True
                    //현재 위치를 넘기기 단, total은 다음 좌표값을 더해서
                    dfs(x,y,cnt+1,total+graph[nextx][nexty])
                    visited[nextx][nexty] = False

                visited[nextx][nexty] = True
                dfs(nextx,nexty,cnt+1,total+graph[nextx][nexty])
                visited[nextx][nexty] = False
result = 0
visited = [[False for i in range(m)] for i in range(n)]
for i in range(n):
    for j in range(m):
        visited[i][j] =True
        dfs(i,j,1,graph[i][j])
        visited[i][j] =False
print(result)