테트로미노 [백준 14500번]

문제

 

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

14500번: 테트로미노

 

내 풀이

ㅗ를 제외한 나머지 테트로미노는 dfs로 만들 수 있다. 그러나 ㅗ는 모양이 요상하게 생겼기 때문에 따로 만들어야 한다.

 

1. ㅗ를 제외한 나머지 테트로미노

늘 사용하는 dfs 코드로 짰다. 백트래킹이기 때문에 재귀를 다 돌리고 난 후 check를 다시 False로 만들어주어야 한다.

 

2. ㅗ

ㅗ로 총 4가지 모양을 만들 수 있다. ㅗ, ㅜ, ㅓ, ㅏ

그래서 제일 처음에 for문을 4번 돌렸고, 방향을 새로 만들어주었다. ndx, ndy

dx, dy 중에서 좌표 한 개만 제외하면 될 것 같았다. 그래서 dx와 dy에서 k 인덱스의 좌표를 제외한 좌표인 ndx, ndy를 만들었다.

ex) k = 1, dx = [-1, 1, 0, 0], dy = [0, 0, 1, -1] -> ndx = [-1, 0, 0], ndy = [0, 1, -1]

ndx, ndy를 사용하여 x, y를 갱신한 후 total을 계산하는 방식이다.

 

import sys
input = sys.stdin.readline

N, M = map(int, input().split())
paper = []
for i in range(N):
    paper.append(list(map(int, input().split())))
dx, dy = [-1, 1, 0, 0], [0, 0, 1, -1]
check = [[False]*M for _ in range(N)]
MAX = 0

def dfs(x, y, cnt, total):
    global MAX
    if cnt == 4:
        MAX = max(MAX, total)
        return
    for i in range(4):
        nx, ny = x+dx[i], y+dy[i]
        if 0<=nx<N and 0<=ny<M and not check[nx][ny]:
            check[nx][ny] = True
            dfs(nx, ny, cnt+1, total+paper[nx][ny])
            check[nx][ny] = False

# ㅗ ㅜ ㅓ ㅏ            
def u(x, y): # x, y가 중심
    global MAX
    for k in range(4):
        total = paper[x][y]
        ndx, ndy = dx[:k]+dx[k+1:], dy[:k]+dy[k+1:]
        for i in range(3):
            nx, ny = x+ndx[i], y+ndy[i]
            if 0<=nx<N and 0<=ny<M:
                total += paper[nx][ny]
        MAX = max(MAX, total)
   
for i in range(N):
    for j in range(M):
        if not check[i][j]:
            check[i][j] = True
            dfs(i, j, 1, paper[i][j])
            check[i][j] = False
            u(i, j)
            
print(MAX)

 

총평

풀긴 했는데, 삼성 기출은 아직까지 나에게 왜이리 어려운지...

"푸는"게 아닌 "풀어내는" 느낌이다. 꾸역꾸역 풀어내기.