[백준] 14500번(python 파이썬) - 테트로미노

문제 링크: https://www.acmicpc.net/problem/14500

14500번: 테트로미노

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답비율
2 초	512 MB	69309	26070	16943	35.678%

문제

폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다.

• 정사각형은 서로 겹치면 안 된다.
• 도형은 모두 연결되어 있어야 한다.
• 정사각형의 변끼리 연결되어 있어야 한다. 즉, 꼭짓점과 꼭짓점만 맞닿아 있으면 안 된다.

정사각형 4개를 이어 붙인 폴리오미노는 테트로미노라고 하며, 다음과 같은 5가지가 있다.

아름이는 크기가 N×M인 종이 위에 테트로미노 하나를 놓으려고 한다. 종이는 1×1 크기의 칸으로 나누어져 있으며, 각각의 칸에는 정수가 하나 쓰여 있다.

테트로미노 하나를 적절히 놓아서 테트로미노가 놓인 칸에 쓰여 있는 수들의 합을 최대로 하는 프로그램을 작성하시오.

테트로미노는 반드시 한 정사각형이 정확히 하나의 칸을 포함하도록 놓아야 하며, 회전이나 대칭을 시켜도 된다.

입력

첫째 줄에 종이의 세로 크기 N과 가로 크기 M이 주어진다. (4 ≤ N, M ≤ 500)

둘째 줄부터 N개의 줄에 종이에 쓰여 있는 수가 주어진다. i번째 줄의 j번째 수는 위에서부터 i번째 칸, 왼쪽에서부터 j번째 칸에 쓰여 있는 수이다. 입력으로 주어지는 수는 1,000을 넘지 않는 자연수이다.

출력

첫째 줄에 테트로미노가 놓인 칸에 쓰인 수들의 합의 최댓값을 출력한다.

 

문제 풀이

---

이 문제는 풀이 방법이 두가지가 있다. 

1. 노가다

-> 2차원 list의 인덱스를 이용해서 나올 수 있는 모든 모양의 index를 저장한 후 모양에 따라 조립한다.

ex) ㅡ 모양의 테트로미노를 생각해보자 시작 지점이 0, 0 이고 테트로미노의 값을 계산해주는 함수에 이 값을 

      매개변수 x, y에 넣어준다고 생각하면 [x+1][y], [x+2][y], [x+3][y], [x+4][y] 와 같이 모든 경우의 수의 방향을 저장한 후 

      모양에 따라 합쳐주면 된다. 그후 값을 비교하면 정답

 

2. dfs

-> 테트로미노를 두가지 종류로 나눌 수 있다 'ㅗ'(욕아님) , 'ㅗ'를 제외한 나머지 테트로미노들

 

이렇게 종류를 나누는 이유는 'ㅗ'을 제외한 나머지 테트로미노는 한쪽끝에서 선 하나로 탐색이 모두 가능하지만

'ㅗ' 모양은 두가지 선으로 나눠져야 탐색이 가능하기 때문이다.  

 

테트로미노 종류나누기 아이디어( 그림이 허접한건 이해 부탁드려요ㅜ )

그림으로 보면 이해가 더 잘될 것이다. dfs를 사용해서 탐색할경우 'ㅗ'을 제외한 나머지 테트로미노는 좌우상하 방향으로 탐색하면 나머지 테트로미노의 모든 방향을 찾을 수 있지만 'ㅗ' 부분은 그게 어렵다.

'ㅗ' 부분은 다음과 같은 방식을 사용하면 쉽게 찾을 수 있다.

방법1. 3개의 방향을 탐색해서 4가지 경우의 수 중 최댓값 찾기

방법2. 4방향 모두를 탐색한 수 그 4방향의 수 중에서 가장 작은 수를 제거한 후 모두 더하기

           -> 어짜피 방법1의 4가지 경우중 최댓값은 4방향의 수 중 가장 작은 수를 제거한 경우이기 때문이다.

 

방법2의 방향이 더 빠르기 때문에 나는 방법2의 방식으로 코드를 작성했다.

 

구현 코드

---

#백준 14500
#테트로미노

n, m = map(int, input().split())
graph = [list(map(int, input().split())) for _ in range(n)] # 입력값 저장
visited = [[False] * m for _ in range(n)] # 방문확인

# 방향설정
dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]

maximum = 0 # 최댓값 저장 변수

# ㅗ 모양을 제외한 나머지 모양 탐색
def dfs(x, y, tmp, cnt):
    global maximum
    if cnt == 4: # 탐색완료 후 최댓값 비교
        maximum = max(maximum, tmp)
        return
    for i in range(4): # 방향 탐색
        nx = x + dx[i]
        ny = y + dy[i]
        if nx<0 or nx>=m or ny<0 or ny>=n or visited[ny][nx]:
            continue
        visited[ny][nx] = True # 방문처리
        dfs(nx, ny, tmp+graph[ny][nx], cnt+1)
        visited[ny][nx] = False # 방문처리 제거

# ㅗ 모양 탐색
def fy(x, y):
    global maximum
    tmp = graph[y][x]
    arr = []
    for i in range(4): # 모든 방향 탐색
        nx = x + dx[i]
        ny = y + dy[i]
        if nx<0 or nx>=m or ny<0 or ny>=n:
            continue
        arr.append(graph[ny][nx])
    length = len(arr)
    if length == 4 : # 만약 4방향 모두 nxm에 들어간다면 그중 가장 작은 값 제거 후 sum
        arr.sort(reverse=True)
        arr.pop()
        maximum = max(maximum, sum(arr) + graph[y][x])
    elif length == 3: # 3방향만 nxm에 들어가기 때문에 바로 sum
        maximum = max(maximum, sum(arr) + graph[y][x])
    return # length가 2 이하라면 ㅗ 모양이 아니므로 바로 return

for i in range(n):
    for j in range(m):
        visited[i][j] = True # 현재 지점 방문처리
        dfs(j, i, graph[i][j], 1)
        fy(j, i)
        visited[i][j] = False

print(maximum) # 정답 출력