백준 14500 테트로미노 - (Python)

문제

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

 

나의 접근법

저는 처음에 풀 방법이 딱 한가지 밖에 생각이 안났습니다. 바로 테트로미노의 모든 회전과 대칭 좌표를 직접 찾아 반복문을 돌려가며 일일이 확인하는 것이었습니다.

그런데 제가 이번에도 문제를 제대로 확인하지 않아 회전만 구하고 대칭은 놓치고 구현했습니다. 그런데 제가 생각한 테트리스에는 대칭이 없어서 문제를 제대로 숙지 안하고 예측하여 푼 것이 화근이었습니다.

어쨌든 대칭까지 구현했는데 역시나 처음에는 틀렸습니다.

다행히 좋은 반례들을 모아놓은 분이 계셔서 그 반례 덕분에 코드 오류를 잡을 수 있었습니다.

그 반례는 맨 아래 첨부하겠습니다.

 

첫번째 코드

def check(tetro):
    x1, y1, x2, y2, x3, y3, x4, y4 = tetro
    result = 0
    for i in range(N):
        for j in range(M):
            nx1, ny1, nx2, ny2, nx3, ny3, nx4, ny4 = x1 + i, y1 + j, x2 + i, y2 + j, x3 + i, y3 + j, x4 + i, y4 + j
            if 0 <= nx1 < N and 0 <= nx2 < N and 0 <= nx3 < N and 0 <= nx4 < N and 0 <= ny1 < M and 0 <= ny2 < M and 0 <= ny3 < M and 0 <= ny4 < M:
               temp = graph[nx1][ny1] + graph[nx2][ny2] + graph[nx3][ny3] + graph[nx4][ny4]
               result = max(temp, result)
    return result

N, M = map(int, input().split())
graph = []
ans = 0
temp_ans = 0
for i in range(N):
    graph.append(list(map(int, input().split())))

tetro1 = [0, 0, 0, 1, 0, 2, 0, 3]
tetro2 = [0, 0, 0, 1, 1, 0, 1, 1]
tetro3 = [0, 0, 1, 0, 2, 0, 2, 1]
tetro4 = [0, 0, 1, 0, 1, 1, 2, 1]
tetro5 = [0, 0, 0, 1, 0, 2, 1, 1]

temp_ans = check(tetro1)
ans = max(ans, temp_ans)

tetro1Rotate = [0, 0, 1, 0, 2, 0, 3, 0]
temp_ans = check(tetro1Rotate)
ans = max(ans, temp_ans)

temp_ans = check(tetro2)
ans = max(ans, temp_ans)

temp_ans = check(tetro3)
ans = max(ans, temp_ans)
tetro3Rotate1 = [0, 0, 0, 1, 0, 2, 1, 0]
temp_ans = check(tetro3Rotate1)
ans = max(ans, temp_ans)
tetro3Rotate2 = [0, 0, 0, 1, 1, 1, 2, 1]
temp_ans = check(tetro3Rotate2)
ans = max(ans, temp_ans)
tetro3Rotate3 = [1, 0, 1, 1, 1, 2, 0, 2]
temp_ans = check(tetro3Rotate3)
ans = max(ans, temp_ans)

tetro3symmetric1 = [0, 1, 1, 1, 2, 1, 2, 0]
temp_ans = check(tetro3symmetric1)
ans = max(ans, temp_ans)
tetro3symmetric2 = [0, 0, 1, 0, 1, 1, 1, 2]
temp_ans = check(tetro3symmetric2)
ans = max(ans, temp_ans)
tetro3symmetric3 = [0, 0, 0, 1, 1, 0, 2, 0]
temp_ans = check(tetro3symmetric3)
ans = max(ans, temp_ans)
tetro3symmetric4 = [0, 0, 0, 1, 0, 2, 1, 2]
temp_ans = check(tetro3symmetric4)
ans = max(ans, temp_ans)

temp_ans = check(tetro4)
ans = max(ans, temp_ans)
tetro4Rortate = [0, 1, 0, 2, 1, 0, 1, 1]
temp_ans = check(tetro4Rortate)
ans = max(ans, temp_ans)

tetro4symmetric1 = [0, 0, 0, 1, 1, 1, 1, 2]
temp_ans = check(tetro4symmetric1)
ans = max(ans, temp_ans)
tetro4symmetric1 = [0, 1, 1, 1, 1, 0, 2, 0]
temp_ans = check(tetro4symmetric1)
ans = max(ans, temp_ans)

temp_ans = check(tetro5)
ans = max(ans, temp_ans)
tetro5Rortate1 = [1, 0, 0, 1, 1, 1, 2, 1]
temp_ans = check(tetro5Rortate1)
ans = max(ans, temp_ans)
tetro5Rortate2 = [0, 1, 1, 0, 1, 1, 1, 2]
temp_ans = check(tetro5Rortate2)
ans = max(ans, temp_ans)
tetro5Rortate3 = [0, 0, 1, 0, 2, 0, 1, 1]
temp_ans = check(tetro5Rortate3)
ans = max(ans, temp_ans)

print(ans)

 

더 깔끔한 코드

def dfs(x, y, depth, total):
  global ans
  # 현재의 depth에서 남은 종이 합이 최댓값이더라도 현재 최대값보다 작다면 리턴
  # 시간 초과를 벗어나기 위해
  if ans >= total + MAX * (4 - depth):
    return
  # 4개를 모두 찾은 경우
  if depth == 4:
    ans = max(ans, total)
    return
  else:
    for dx, dy in (-1, 0), (1, 0), (0, -1), (0, 1) :
      nx = x + dx
      ny = y + dy
      if 0 <= nx < N and 0 <= ny < M and not visited[nx][ny]:
        #ㅗ 모양을 위해, 2개 칸을 선택하면 자기 자신을 시작점으로 dfs 호출
        if depth == 2:
          visited[nx][ny] = True
          dfs(x, y, depth + 1, total + arr[nx][ny])
          visited[nx][ny] = False
        visited[nx][ny] = True
        dfs(nx, ny, depth + 1, total + arr[nx][ny])
        visited[nx][ny] = False

N, M = map(int, input().split())
arr = [list(map(int, input().split())) for _ in range(N)]
visited = [[False] * M for _ in range(N)]
dr = [-1, 0, 1, 0]
dc = [0, 1, 0, -1]
ans = 0
# 종이에서 가장 큰 값 => 나중에 백트래킹을 위해
MAX = max(map(max, arr))

for x in range(N):
   for y in range(M):
       visited[x][y] = True
       dfs(x, y, 1, arr[x][y])
       # 다른 dfs에서 방문을 하기 위해 변경
       visited[x][y] = False

print(ans)

위 코드에서 대단한 점은 ㅗ 모양을 따로 구현하지 않고 dfs로 같이 구현했다는 점입니다. 다른 다음 nx, ny 를 dfs에 넣어 탐색하는 것이 아니라 자기 자신을 넣어 시작점을 자기자신으로 초기화 했습니다.

 

후기

솔직히 제 첫번째 코드는 무식한 방법이라고 생각했는데 시험장에 가면 이렇게 방법이 떠오른는 것만으로도 감사하다는 생각으로 풀었고 정답을 맞은 후에 사람들이 어떻게 풀었는지 궁금하여 검색을 해봤고 그제서야 왜 대칭이 있었는지 확인할 수 있었습니다. 

O
O	O
	O

한 점에서 DFS로 백트래킹을 이용하여 depth를 4까지 가면 'ㅗ' 모양을 제외한 모든 테트로미노의 모양을 찾을 수 있기 때문입니다. 대칭이 없다면 위 방법에 여러가지 조건이 붙겠지만 대칭이 있어 dfs만으로 쉽게 해결할 수 있는 문제인 것 같습니다. 위 방법을 보고 제 코드가 너무 무식했고 2번째 같은 클린 코드를 배워서 많이 보고 배워서 비슷하게 짜보도록 하겠습니다. 

 

참고 - 19개 반례

https://www.acmicpc.net/board/view/61597 이분의 도움으로 빠르게 문제점을 확인할 수 있었습니다.

//19
4 4
0 0 0 0
0 0 0 0
0 0 0 0
1 2 3 4
4 4
0 0 0 1
0 0 0 2
0 0 0 3
0 0 0 4
4 4
0 0 0 0
0 0 0 0
0 0 1 2
0 0 3 4
4 4
0 0 0 0
0 0 1 0
0 0 2 0
0 0 3 4
4 4
0 0 0 0
0 0 0 0
0 1 2 3
0 4 0 0
4 4
0 0 0 0
0 0 1 2
0 0 0 3
0 0 0 4
4 4
0 0 0 0
0 0 0 0
0 0 0 1
0 4 3 2
4 4
0 0 0 0
0 0 0 1
0 0 0 2
0 0 4 3
4 4
0 0 0 0
0 0 0 0
0 1 0 0
0 2 3 4
4 4
0 0 0 0
0 0 2 1
0 0 3 0
0 0 4 0
4 4
0 0 0 0
0 0 0 0
0 1 2 3
0 0 0 4
4 4
0 0 0 0
0 0 0 1
0 0 2 3
0 0 4 0
4 4
0 0 0 0
0 0 1 0
0 0 2 3
0 0 0 4
4 4
0 0 0 0
0 0 0 0
0 1 2 0
0 0 3 4
4 4
0 0 0 0
0 0 0 0
0 0 3 4
0 1 2 0
4 4
0 0 0 0
0 0 0 1
0 0 2 3
0 0 0 4
4 4
0 0 0 0
0 0 1 0
0 0 2 3
0 0 4 0
4 4
0 0 0 0
0 0 0 0
0 0 1 0
0 2 3 4
4 4
0 0 0 0
0 0 0 0
0 1 2 3
0 0 4 0