[백준] 14500 파이썬(python) : 테트로미노 - 백트래킹(dfs)

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

14500번: 테트로미노

 

 

import sys
n, m = map(int, sys.stdin.readline().split())
graph = [ list(map(int, sys.stdin.readline().split())) for _ in range(n)]
visit = [ [0]*m for _ in range(n) ]
dx = [ -1, 1, 0, 0 ]
dy = [ 0, 0, -1, 1 ]
ans = 0
max_value = max(map(max, graph))

def dfs(x, y, idx, total):
    global ans
    if ans >= total + max_value * (3-idx): #1
        return
    if idx == 3:
        ans = max(ans, total)
        return
    else:
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < n and 0 <= ny < m and not visit[nx][ny]: 
                if idx == 1: #2
                    visit[nx][ny] = 1
                    dfs(x, y, idx+1, total+graph[nx][ny])
                    visit[nx][ny] = 0
                visit[nx][ny] = 1
                dfs(nx, ny, idx+1, total+graph[nx][ny])
                visit[nx][ny] = 0

for i in range(n):
    for j in range(m):
        if not visit[i][j]:
            visit[i][j] = 1
            dfs(i, j, 0, graph[i][j])
            visit[i][j] = 0
print(ans)

 

원래는 다른 블로그를 참고해도 나의 방식으로 다시 설명해서 기록해 놓는데 이번엔 이것보다 더 좋게 설명할 수 없을 것 같아서 블로그 링크를 걸어 놓겠다. 

 

#1 : 지금까지 모은 ans값이 total + (3-idx)*max_value를 초과하게 될 수는 없다. 그래서 return을 해서 그런 경우는 차단을 해주면 횟수를 줄일 수 있다.

#2 : ㅗ모양의 블록을 포함한 다른 모든 블록모양을 완전탐색으로 만들 수 있게 된다.

 

설명은 여기서

https://cijbest.tistory.com/87

[백준 14500 : PYTHON] 테트로미노

 

코드는 여기서 가져왔다.

https://velog.io/@jajubal/파이썬백준-14500-테트로미노

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

 

 

문제를 처음보고 어떻게 회전과 대칭을 표현할지 막막했는데 블록 하나하나를 추가해가는 방식이란걸 블로그 설명을 읽고 깨달았다. codeplus+에서는 알고리즘 기초 2/2에 포함된 문제여서 시도했는데 변형된 dfs문제였다. 백트래킹을 이용해서 탈출조건을 만들어놔서 recursionlimit에도 걸리지 않은 것 같다.

브르투포스는 그래프이론의 기초가 되는 알고리즘인 만큼 더 많은 문제를 풀고 열심히 공부해야겠다.

 

https://hgk5722.tistory.com/212

[Algorithm] BackTracking(백트래킹) 알고리즘