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

def BOJ14500() :
  global result
  n,m = map(int, input().split())
  graph = []
  for _ in range(n) :
    graph.append(list(map(int, input().split())))
  visited = [[0] * m for _ in range(n)]
  direction = [[0,1], [0,-1], [1,0], [-1,0]]
  result = 0
  middle_finger_tetromino = [[[0,1], [0,2], [1,1]], [
      [0,1], [0,2], [-1,1]], [[1,0], [2,0], [1,1]], [[1,0], [2,0], [1,-1]]]

  def dfs(x, y, count, number, visited):
    global result
    if count == 4 :
      result = max(result, number)
      return
    for dir in direction:
      dir_x, dir_y = dir
      next_x = dir_x + x
      next_y = dir_y + y
      if 0 <= next_x < n and 0 <= next_y < m and visited[next_x][next_y] == 0:
        visited[next_x][next_y] = 1
        dfs(next_x, next_y, count+1, number + graph[next_x][next_y], visited)
        visited[next_x][next_y] = 0
    
  def middle_finger(x, y) :
    global result
    for tetromino in middle_finger_tetromino :
      flag = True
      temp = graph[x][y]
      for dir in tetromino :
        dir_x, dir_y = dir
        next_x = x + dir_x
        next_y = y + dir_y
        if 0 <= next_x < n and 0 <= next_y < m :
          temp += graph[next_x][next_y]
        else :
          flag = False
          break
      if flag :
        result = max(result, temp)

  for x in range(n) :
    for y in range(m) :
      visited[x][y] = 1
      dfs(x, y, 1, graph[x][y], visited)
      visited[x][y] = 0
      middle_finger(x, y)

  print(result)

BOJ14500()


# https://pacific-ocean.tistory.com/364

 

접근 방법 :

1. 테트로미노를 가운데가 오목한 형태만 제외하고 보면 시작점에서 네개를 연속으로 이동한 것으로 볼 수 있다고 생각했다.  (가운데가 오목한 형태는 한 점이 연속으로 4번 움직인 경우가 아니라 따로 정의해 주고자 하였다)

2. 회전과 대칭또한 4개를 연속으로 이동하는 경우에 포함되어 있다고 판단했다.

3. 하나의 점에서 여러 경우의 수(회전, 대칭, 다른 도형의 형태)로 뻗어 나갈 수 있다고 생각해서 백트래킹을 도입했다(visited[x] = 1, dfs(), visited[x] = 0)

4. 이렇게 한번의 dfs로 경우의 수를 탐색하고 해당 지점에서 가운데가 오목한 형태를 고려해 주었다.

5. 모든 지점을 한번씩 탐색 하는데 dfs로 4개의 도형의 회전, 대칭을 다 고려해주고 가운데가 오목한 형태까지 고려해주어서 최댓값을 비교하였다.

 

장애물 이였던 것 :

1. dfs 개념을 생각하지 못했고 결국 다른 분의 설명을 참고하였다(아래에 출처로 기록해두었다)

2. 처음에는 문제에 정의되어있는 5가지의 경우를 일일히 변수로 정의하여 회전이나 대칭을 가정한후 해당 배열에 포함된 값들을 더했었다(왜 그랬어??)

  # 테트로미노 종류는 5가지
  tetromino = [[[0,0], [0,1], [0,2], [0,3]], [[0,0], [1,0], [0,1], [1,1]],
               [[0,0], [1,0], [2,0], [2,1]], [[0,0], [1,0], [1,1], [2,1]], 
               [[0,0], [0,1], [0,2], [1,1]]]

3. 2번 개념으로 접근을 하려니 예외 처리가 너무 많아졌었다. 코드길이가 4000 byte를 넘어가기 시작해서 이건 아니다 싶었다.

 

 

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

14500번: 테트로미노

https://pacific-ocean.tistory.com/364

[백준] 14500번(python 파이썬)