[백준] 14500번 파이썬 _ 테트로미노

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

14500번: 테트로미노

문제유형 : 구현, 완탐 (dfs)

 

문제풀이 :

• 문제의 키포인트
  • ㅗ모양은 그냥 일반적으로 count가 4가되면 리턴하는 dfs로는 해결할 수 없음. 따로 처리를 해줘야함
    • 나는 외부에서 따로 처리를 했는데
    • dfs수행에서 블록개수가 2인 시점에서 다시 자기자신을 시작점으로하는 dfs를 호출하면 된다.. (다른분 풀이 아래참고) 
  • dfs를 수행할때 겹치는 모양이 계속해서 나오게되는데 이것을 어떻게 조기종료 시킬것인가..
    • 현재의 dfs에서 남은블록(4개에 다다를때까지)이 모두 최댓값이라고해도 현재의 최대를 넘길수 없다면 더이상 볼필요가 없으므로 조기종료해야함!!! ( 이 코드를 추가해야 시간초과가 안남 )

 

 

정답코드 : 

#결국 다 봐야함
# count가 4가 되는순간 최대합을 갱신한다.
# dfs, 시작지점 0,0, 이동가능한지 확인,

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

result = 0

def dfs(s_x, s_y, cnt, sum):
    global result, max_val
    visited[s_x][s_y] = True

    # 남은 블럭이 모두 최댓값이라 해도 현재의 최대를 넘길수 없을때 조기종료 해버림
    if sum + max_val * (4-cnt) <= result:
        return

    # 사각형 4개가 된 순간 최댓값을 갱신한다.
    if cnt == 4:
        result = max(result, sum)
        return

    # 상하좌우 이동
    for i in range(4):
        # 이동가능하면
        d_x, d_y = s_x+dx[i], s_y+dy[i]
        if 0<=d_x<n and 0<= d_y <m and not visited[d_x][d_y]:
                dfs(d_x,d_y, cnt+1, sum+graph[d_x][d_y])
                visited[d_x][d_y] = False # 목적지를 풀어주는것임

def adjust(graph, s_x, s_y):
    global result
    adj = []
    for i in range(4):
        # 이동가능하면
        if s_x+dx[i] >=0 and s_x+dx[i]<n and s_y+dy[i] >=0 and s_y+dy[i] <m:
            adj.append(graph[s_x+dx[i]][s_y+dy[i]])

    if len(adj)>=3:
        temp = graph[s_x][s_y]+sum(sorted(adj, reverse=True)[:3])
        result = max(result, temp)


import sys
input = sys.stdin.readline

n,m = map(int, input().split()) #세로-n-행, 가로-m-열

graph = []

visited = [[False] * m for _ in range(n)]

for _ in range(n):
    graph.append(list(map(int, input().split())))

max_val = max(max(*graph))

#adjust(graph, 2,3)
#dfs(graph, 3,1,0,graph[3][1], visited)

for i in range(n):
    for j in range(m):
        dfs(i,j,1,graph[i][j])
        visited[i][j] = False
        adjust(graph, i,j)

print(result)

 

다른분 더 좋은풀이 : 

ㅗ자 의 처리를 나처럼 아예 밖에서 따로한것이아니라 dfs수행중에 2까지일때 시작점을 자기자신으로 하는 dfs를 호출함으로서 해결

import sys
input = lambda : sys.stdin.readline()

move = [(-1,0),(1,0),(0,-1),(0,1)]
def dfs(r, c, depth, s):
    global max_value
    if s + maxv*(4-depth) <= max_value:
        return        
    if depth >= 4:
        if max_value < s:
            max_value = s
        return
    else:
        for dr, dc in move:
            nr, nc = r + dr, c + dc
            if 0 <= nr < n and 0 <= nc < m and visited[nr][nc] == 0:
                if depth == 2:
                    visited[nr][nc] = 1
                    dfs(r, c, depth + 1, s + board[nr][nc])
                    visited[nr][nc] = 0

                visited[nr][nc] = 1
                dfs(nr, nc, depth + 1, s + board[nr][nc])
                visited[nr][nc] = 0


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

maxv = max(map(max, board))

max_value = 0
visited = [[0]*m for _ in range(n)]
for i in range(n):
    for j in range(m):
        visited[i][j] = 1
        dfs(i,j,1,board[i][j])
        visited[i][j] = 0

print(max_value)