[백준][python]14500 테트로미노

문제

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

소스코드

import sys
input = sys.stdin.readline
from itertools import combinations

if __name__ == "__main__":
    n,m = map(int,input().split())
    arr = [list(map(int,input().split())) for _ in range(n)]
    answer = 0
    visited = [[0] * m for _ in range(n)]
    move = [[1,0],[-1,0],[0,1],[0,-1]] # 상,하,좌,우

    # ㅗ 제외 테트로미노 체크
    def dfs(l,x,y,tmp_sum):
        global answer
        if l == 4: # 폴리오미노 4개를 두면 테트로미노
            answer = max(answer,tmp_sum)
            return
        for k in range(4): # 이전과 연속해서 상하좌우 체크
            xx = x + move[k][0]
            yy = y + move[k][1]
            if 0 <= xx < n and 0 <= yy < m and not visited[xx][yy]:
                visited[xx][yy] = 1
                dfs(l+1,xx,yy,arr[xx][yy]+tmp_sum)
                visited[xx][yy] = 0 # 반드시 백트래킹

    # ㅗ 테트로미노 체크
    def chk(x,y):
        global answer
        for ch in list(combinations([i for i in range(4)],3)): # 중심 제외 상하좌우 중 3개 선택해서 체크해야 함
            tmp = arr[x][y] # 초기값은 가운데 중심
            for c in ch: # 상하좌우 중 3개 선택한 값 체크
                xx = x + move[c][0]
                yy = y + move[c][1]
                if 0 <= xx < n and 0 <= yy < m:
                    tmp += arr[xx][yy]
                else: #경로 이탈하면
                    tmp = 0 #전부 탈락 이 테트로미노는 못들어옴
                    break
            answer = max(answer,tmp)

    for i in range(n):
        for j in range(m):
            # ㅗ 제외 테트로미노 체크
            visited[i][j] = 1
            dfs(1,i,j,arr[i][j])
            visited[i][j] = 0
            # ㅗ 테트로미노 체크
            chk(i,j)

    print(answer)

설명

백트래킹을 이용해서 테트로미노를 만든 후 최대값을 구해준다

이때 ㅗ 모양은 만들 수 없으므로 따로 처리해준다

 

(0,0)부터 방문처리를 한 후 dfs 탐색

1. 상하좌우를 체크한다 
2. (상,좌)는 범위는 벗어남 (하)를 체크하고 dfs 탐색 - 아래 그림 2 표시
3. (상)은 이미 체크 (좌)는 범위 벗어남 (하) 체크하고 dfs 탐색 - 아래 그림 3표시
4. (상)은 이미 체크 (좌)는 범위 벗어남 (하) 체크하고 dfs 탐색 - 아래 그림 3표시
5. 총 4개가 체크됬기 때문에 문제에서 말한 테트로미가 완성됨을 확인가능 최대값을 체크해준다

 

테트로미가 완성됬으므로 백트래킹을 해줘서 다른 테트로미를 만든다

위의 4번에서 (하)까지 체크했으니 이번엔 (우)를 체크해서 테트로미를 완성 후 최댓값을 구해준다

 

위와 같은 방식으로 백트래킹을 수행하면 ㅗ 모양을 제외한 모든 테트로미를 만들 수 있다

 

ㅗ 모양 테트로미는 가운데를 중심으로 (상,하,좌,우) 중 3개 영역만 체크하면 테트로미를 만들 수 있다

기존에 초기화한 move 배열중 조합을 사용해서 4개중 3개를 선택 후 반복문을 사용해 최댓값을 구해준다

이때 하나라도 범위가 벗어나면 더 이상 최댓값을 구하지 않고 다음 테트로미를 만들어준다