[백준]14500번: 테트로미노(Python)

문제 링크

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

14500번: 테트로미노

 

풀이

풀이 설명

• 분류: 구현, 완전탐색
• 우선 한 좌표를 시작점이라고 생각하고 5가지 블록 * 4(회전) * 2(대칭) * 모든 좌표(500*500) = 1천만 -> 2초이므로 완탐 가능
• 5가지 블럭 모양에 대해 회전, 대칭을 다 그려본다.
  • 그러면 네모 모양과 막대 모양, ㅜ 모양, 복잡한 꺾인 모양은 8가지로 안만들어도 돌려도 같은 모양인 경우가 나올 것이다. 
  • 이를 제외하면 총 19가지가 나왔다. (자세한건 코드 주석 참고)
  • 노가다지만 이렇게 하는게 완탐에선 제일 좋은듯(물론 통과해서 하는 소리^.^)
• 한 블럭 모양이 채워질 때마다 결과값과 비교한다.

코드

N, M = map(int, input().split())

maps = []
for _ in range(N):
    maps.append(list(map(int, input().split())))

blocks = []
# 긴 블럭
blocks.append([(0, 0), (0, 1), (0, 2), (0, 3)])
blocks.append([(0, 0), (1, 0), (2, 0), (3, 0)])
# 네모 블럭
blocks.append([(0, 0), (1, 0), (0, 1), (1, 1)])
# 복잡 블럭
blocks.append([(0, 0), (1, 0), (1, 1), (2, 1)])
blocks.append([(0, 0), (0, 1), (-1, 1), (-1, 2)])
blocks.append([(0, 0), (0, 1), (1, 1), (1, 2)])
blocks.append([(0, 0), (1, 0), (1, -1), (2, -1)])
# 우 블럭
blocks.append([(0, 0), (0, 1), (0, 2), (1, 1)])
blocks.append([(0, 0), (0, 1), (0, 2), (-1, 1)])
blocks.append([(0, 0), (1, 0), (2, 0), (1, 1)])
blocks.append([(0, 0), (1, 0), (2, 0), (1, -1)])
# 니은 블럭
blocks.append([(0, 0), (1, 0), (2, 0), (2, 1)])
blocks.append([(0, 0), (-1, 0), (-2, 0), (-2, 1)])
blocks.append([(0, 0), (0, 1), (0, 2), (-1, 2)])
blocks.append([(0, 0), (-1, 0), (-2, 0), (-2, -1)])
blocks.append([(0, 0), (0, -1), (0, -2), (1, -2)])
blocks.append([(0, 0), (0, 1), (0, 2), (1, 2)])
blocks.append([(0, 0), (1, 0), (2, 0), (2, -1)])
blocks.append([(0, 0), (0, -1), (0, -2), (-1, -2)])

result = 0
for x in range(N):
    for y in range(M):
        for block in blocks:
            temp = 0
            for i in range(4):
                nx = x + block[i][0]
                ny = y + block[i][1]
                if nx < 0 or nx >= N or ny < 0 or ny >= M:
                    break
                temp += maps[nx][ny]
            # block 한개 끝나면 비교
            result = max(result, temp)

print(result)