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

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

14500번: 테트로미노

처음에 문제를 잘못읽고

저 블록들을 그림에 채워넣을 때

최대를 구하라는 뜻인줄 알고

이게 무슨 x같은 문제인가 욕하다가

아...하나만 하라고...

하면서 급 빵긋.

이 문제는 원초적으로 풀이하는 방법은

구현으로 모든 케이스를 구하는 경우입니다.

이 문제에서 가장 헷갈리는 부분이

생각보다 저걸 구현할 때

좌표가 헷갈릴 때가 많았습니다.

제가 구현한 아이디어는 얼추 맞았는데

(이렇게 맞았다고 생각했던 건

가장 쉬운 케이스인

일짜와 사각형은 맞았기 때문이고

그걸 토대로 다른 도형도 만들었기 때문에

큰 틀에서는 맞았구나 라고 생각)

저 구현하는 게 자꾸 틀려서

애를 먹었습니다.

그래서 결국

직접 저렇게 손으로 쓰면서

구현하는 케이스를 하나 하나씩 다 적었습니다.

 

#백준 14500 테트로미노

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

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


long=[[(0,0),(0,1),(0,2),(0,3)],[(0,0),(1,0),(2,0),(3,0)]]
square=[[(0,0),(0,1),(1,0),(1,1)]]
b_1=[[(0,0),(0,1),(-1,0),(-2,0)],[(0,0),(-1,0),(-1,1),(-1,2)],[(0,0),(0,1),(1,1),(2,1)],[(0,0),(0,1),(0,2),(-1,2)],
     [(0,0),(0,1),(1,0),(2,0)],[(0,0),(-1,0),(0,1),(0,2)],[(0,0),(0,1),(-1,1),(-2,1)],[(0,0),(0,1),(0,2),(1,2)]]
b_2=[[(0,0),(1,0),(1,1),(2,1)],[(0,0),(0,1),(1,1),(1,2)],[(0,0),(1,0),(1,-1),(2,-1)],[(0,0),(0,-1),(1,-1),(1,-2)]]
b_3=[[(0,0),(0,1),(0,2),(1,1)],[(0,0),(0,1),(-1,1),(1,1)],[(0,0),(0,1),(-1,1),(0,2)],[(0,0),(-1,0),(1,0),(0,1)]]


#벽돌 케이스 다 넣고 최대합을 구한다는 알고리즘 구성

max_sum=-1e9

for x in range(N):
  for y in range(M):
    #가장 긴 거
    for s in long:
      now_sum=0
      no=0
      for move in s:
        nx=x+move[0]
        ny=y+move[1]
        #print(nx,ny)
        if (nx<0 or nx>=N) or (ny<0 or ny>=M):
          #print("out")
          no=1
          break
        now_sum+=A[nx][ny]
      if no==0:
        max_sum=max(max_sum,now_sum)
    #정사각형
    for s in square:
      #print(s)
      now_sum=0
      no=0
      for move in s:
        nx=x+move[0]
        ny=y+move[1]
        if (nx<0 or nx>=N) or (ny<0 or ny>=M):
          no=1
          break
        now_sum+=A[nx][ny]
      if no==0:
        max_sum=max(max_sum,now_sum)
    #총모양
    for s in b_1:
      #print(s)
      now_sum=0
      no=0
      for move in s:
        nx=x+move[0]
        ny=y+move[1]
        if (nx<0 or nx>=N) or (ny<0 or ny>=M):
          no=1
          break
        now_sum+=A[nx][ny]
      if no==0:
        max_sum=max(max_sum,now_sum)
    #...모양
    for s in b_2:
      #print(s)
      now_sum=0
      no=0
      for move in s:
        nx=x+move[0]
        ny=y+move[1]
        if (nx<0 or nx>=N) or (ny<0 or ny>=M):
          no=1
          break
        now_sum+=A[nx][ny]
      if no==0:
        max_sum=max(max_sum,now_sum)
    #철 9 모양
    for s in b_3:
      #print(s)
      now_sum=0
      no=0
      for move in s:
        nx=x+move[0]
        ny=y+move[1]
        if (nx<0 or nx>=N) or (ny<0 or ny>=M):
          no=1
          break
        now_sum+=A[nx][ny]
      if no==0:
        max_sum=max(max_sum,now_sum)

print(max_sum)

 

이렇게 푸는 방식은

부지런하게는 풀지만

스마트하지는 못하다고도 볼 수 있죠.

물론 풀이하는 입장에서는

'맞으면 장땡'이긴하지만

다른 문제에 적용하기는 힘든 부분도 있고

저렇게 손으로 나열하다가

케이스 하나만 잘못 적어도

틀렸다고 뜨기때문에

처음부터 다시 다 뒤져야합니다.

그래서 좀 더 스마트한 방식은

DFS를 사용하는 방식입니다.

가운데 손가락 모양빼고

다른 4개의 모형들은

DFS기준으로

3칸을 움직였을 때 나오는 모형들입니다.

그래서 가운데손가락 모양은 냅두고

다른 케이스에서

DFS를 구현했습니다.

 

# 백준 14500 테트로미노-DFS버전

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

A = [list(map(int, input().split())) for _ in range(N)]
c_9 = [[(0, 0), (0, 1), (0, 2), (1, 1)], [(0, 0), (0, 1), (-1, 1), (1, 1)], [(0, 0), (0, 1), (-1, 1), (0, 2)],
       [(0, 0), (-1, 0), (1, 0), (0, 1)]]
max_sum = -1e9
visited = [[False] * M for _ in range(N)]


def dfs(x, y, idx, tmp_sum):
    global max_sum
    if idx == 3:
        max_sum = max(max_sum, tmp_sum)
        return

    if x - 1 >= 0:
        if visited[x - 1][y] == False:
            visited[x - 1][y] = True
            dfs(x - 1, y, idx + 1, tmp_sum + A[x - 1][y])
            visited[x - 1][y] = False
    if x + 1 < N:
        if visited[x + 1][y] == False:
            visited[x + 1][y] = True
            dfs(x + 1, y, idx + 1, tmp_sum + A[x + 1][y])
            visited[x + 1][y] = False
    if y - 1 >= 0:
        if visited[x][y - 1] == False:
            visited[x][y - 1] = True
            dfs(x, y - 1, idx + 1, tmp_sum + A[x][y - 1])
            visited[x][y - 1] = False
    if y + 1 < M:
        if visited[x][y + 1] == False:
            visited[x][y + 1] = True
            dfs(x, y + 1, idx + 1, tmp_sum + A[x][y + 1])
            visited[x][y + 1] = False


for x in range(N):
    for y in range(M):
        for s in c_9:
            # print(s)
            now_sum = 0
            no = 0
            for move in s:
                nx = x + move[0]
                ny = y + move[1]
                if (nx < 0 or nx >= N) or (ny < 0 or ny >= M):
                    no = 1
                    break
                now_sum += A[nx][ny]
            if no == 0:
                max_sum = max(max_sum, now_sum)
        visited[x][y] = True
        dfs(x, y, 0, A[x][y])
        visited[x][y] = False

print(max_sum)

 

뭐가 더 좋은 풀이인지는

사람마다 다르겠지만

공부하는 입장에서는

여러가지를 생각해보는 것도 좋을 것 같습니다^^