[BaekJoon] 백준 14500번 테트로미노

[BaekJoon] 백준 14500번 테트로미노

 

🎈문제

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

💬설명

• 어려운 문제는 아니었는데 어떻게든 bfs로 풀어보려고 하다가 오래 걸렸다. 결국 bfs로 못품..
• bfs로 푸는 경우 ㅁ 모양의 테트로미노를 처리할 수 없어서 visit 여부를 체크하지 말아야 하는데 그 경우 시간 초과가 난다. 그럼 visit 배열을 다시 추가해야 하고 그럼 ㅁ 모양을 처리할 수 없고,, 무한 반복,,ㅠㅠ
• 결국 dfs -> 백트래킹으로 풀었더니 5분만에 풀었다.
• 포인트
  1. dfs -> 백트래킹으로 하나씩 들어가면서 풀어줌
  2. 4개가 완성되면 max_value 업데이트
  3. ㅓ, ㅏ, ㅗ, ㅜ 모양의 경우 dfs로 처리할 수 없어 예외로 따로 코드를 짜줌

👩‍💻코드

# BaekJoon14500.py
from collections import deque
import sys


input = sys.stdin.readline
N, M = map(int, input().split())
arr = [[] for _ in range(N)]
for i in range(N):
    arr[i] = list(map(int, input().split()))
dx = [0, 0, -1, 1]
dy = [1, -1, 0, 0]
visited = [[False for _ in range(M)] for _ in range(N)]
max_sum = -1


def dfs(x, y, num, summ):
    global N, M, arr, dx, dy, max_sum
    if num == 4:
        max_sum = max(max_sum, summ)
        return

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

        if nx < 0 or ny < 0 or nx >= N or ny >= M:
            continue
        if not visited[nx][ny]:
            visited[nx][ny] = True
            dfs(nx, ny, num + 1, summ + arr[nx][ny])
            visited[nx][ny] = False


def solution():
    global N, M, arr, max_sum

    for i in range(N):
        for j in range(M):
            visited[i][j] = True
            dfs(i, j, 1, arr[i][j])
            visited[i][j] = False
            # ㅓㅗㅜㅏ모양 검사
            # ㅏ
            if i < N - 2 and j < M - 1:
                max_sum = max(max_sum, arr[i][j] + arr[i+1][j] + arr[i+1][j+1] + arr[i+2][j])
            # ㅜ
            if i < N - 1 and j < M - 2:
                max_sum = max(max_sum, arr[i][j] + arr[i][j+1] + arr[i][j+2] + arr[i+1][j+1])
            # ㅗ
            if i >= 1 and j < M - 2:
                max_sum = max(max_sum, arr[i][j] + arr[i-1][j+1] + arr[i][j+1] + arr[i][j+2])
            # ㅓ
            if 1 <= i < N - 1 and j < M - 1:
                max_sum = max(max_sum, arr[i][j] + arr[i-1][j+1] + arr[i][j+1] + arr[i+1][j+1])


solution()
print(max_sum)