[BOJ] 테트로미노

---

코드

# 다른 분의 로직임
import sys
input = sys.stdin.readline

def dfs(x, y, step, total):
    global answer;
    
    # 남은 블록으로 최대값을 만들 수 없으면 종료
    if total + max_val*(4-step) <= answer:
        return
    
    # 종료조건2
    if step == 4:
        answer = max(answer, total)
        return

    for dx, dy in d:
        nx = x + dx
        ny = y + dy
        
        if 0 <= nx < N and 0 <= ny < M and not visited[nx][ny]:
            # 2번째 블록 연결 후 'ㅏ','ㅓ','ㅗ','ㅜ' 만들기
            if step == 2:
                visited[nx][ny] = True
                # 새로운 좌표에서 탐색하지 않고 기존 좌표로 돌아와 탐색재개
                dfs(x, y, step+1, total+graph[nx][ny])
                visited[nx][ny] = False
            
            # 새로운 블록 붙이기
            visited[nx][ny] = True
            dfs(nx, ny, step+1, total+graph[nx][ny])
            visited[nx][ny] = False

N, M = map(int, input().split())
graph = [list(map(int, input().split())) for _ in range(N)]
max_val = max(map(max, graph)) # 모든 좌표 중 최댓값
d = [(-1, 0), (1, 0), (0, -1), (0, 1)]
visited = [[False] * M for _ in range(N)]
answer = 0

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(answer)

결과

풀이 방법

• 처음에 떠올린 방법 두 가지는 브루트 포스와 DFS이다.
• 브루트 포스로 해결하려면 회전을 고려한 모든 테트로미노를 좌표로 표현하여 graph 밖으로 나가지 않는 선에서 숫자들의 합을 비교하면 되지만 코드 길이가 길어지고 훌륭한 해결방법은 아니다.
• 두 번째 방법은 DFS이다. 이 문제는 테트로미노를 회전시킬 수 있기 때문에 이미 방문한 점을 다시 방문할 수 있어야 한다. => 백트래킹
• 내부적으로 큐를 사용하여 인접한 점들을 우선적으로 방문하는 BFS는 스택(재귀)을 사용하는 DFS와는 달리 백트래킹할 수 없다.
• DFS로 이미 방문한 점을 재방문하려면 DFS 수행 전에 해당 점을 방문처리했다가 DFS 수행을 마치면 방문기록을 제거하면 된다.
  
  
• DFS를 사용했을 때 한 가지 더 고려해야 하는 것은, 'ㅏ, ㅓ, ㅗ, ㅜ' 모양의 테트로미노를 그냥 DFS로는 구현할 수 없다는 점이다. 나머지 모양들은 DFS로 만들 수 있다.
• 따라서 위 4가지 모양을 예외 처리하는 방법은 2가지가 있다. 하나는 해당 모양들을 브루트포스처럼 좌표로 표현하는 방법이고, 나머지 하나는 다른 분의 풀이를 참고한 것인데 다음과 같다.
• 블록 2개를 붙이고 3번째 블록(2번째 블록의 인접 블록 중 방문하지 않은 블록)에서는, 새로운 블록을 해당 블록에서 찾지 않고 기존 블록(2번째 블록)에서 찾도록 따로 처리하면 된다.
• 또 하나 좋았던 코드는 bfs()의 수행횟수를 줄이기 위해 남은 블록들로 최대값을 만들 수 없을 때 바로 종료하는 코드이다.

---