14500번 - 테트로미노

문제

 

14500번: 테트로미노 (acmicpc.net)

14500번: 테트로미노

풀이 1

언뜻 보면 흔한 DFS 문제같지만... 사실 아니다! 테트로미노 중 오른쪽 하단에 보이는 모양은 흔히 쓰는 '한 칸 씩 전진하는 DFS'로 만들수 없기 때문이다. 따라서 총 세가지 방법 정도를 생각할 수 있고, 두 가지 방법을 이용해 풀이했다.

DFS

DFS로 만들 수 없는 모양을 제외한 모든 모양을 DFS로 만들어 탐색하고, 문제의 'ㅏ' 모양에 대해서만 90도 씩 회전하며 탐색한다. 2700ms의 실행시간이 소요된다.

n,m = map(int,input().split())
board = []
for _ in range(n):
    board.append(list(map(int, input().split())))

tetromino = [(0,1),(1,1),(0,2)]

dRow = [-1,0,1,0]
dCol = [0,-1,0,1]


def dfs(row,col,visited,sum_value):
    global max_value
    if len(visited) == 4:
        max_value = max(max_value,sum_value)
        return
    for i in range(4):
        nRow,nCol = row+dRow[i],col+dCol[i]
        if 0 <= nRow < n and 0 <= nCol < m and not (nRow,nCol) in visited:
            visited.add((nRow,nCol))
            sum_value += board[nRow][nCol]
            dfs(nRow,nCol,visited,sum_value)
            visited.remove((nRow,nCol))
            sum_value -= board[nRow][nCol]


def rotate_cw_90(vectors):
    result = []
    for vector in vectors:
        result.append((vector[1],-vector[0]))
    return result


max_value = -int(1e9)
for row in range(n):
    for col in range(m):
        dfs(row,col,set([(row,col)]),board[row][col])
        for _ in range(4):
            tetromino = rotate_cw_90(tetromino)
            sum_value = board[row][col]
            for vector in tetromino:
                nRow,nCol = row+vector[0],col+vector[1]
                if not (0 <= nRow < n and 0 <= nCol < m):
                    break
                sum_value += board[nRow][nCol]
            else:
                max_value = max(max_value,sum_value)

print(max_value)

완전 탐색

미리 테트로미노 모양을 전부 만들어놓고 90도씩 돌려가며 완전탐색한다. 주의할 점은 왼쪽 하단과 왼쪽 중앙 모양은 뒤집은 모양까지 고려해줘야 한다는 것이다. 970 ms 가 소요됐다.

import sys
input = sys.stdin.readline
n,m = map(int,input().split())
board = []
for _ in range(n):
    board.append(list(map(int, input().split())))

tetrominoes = [
    [(0,1),(1,1),(0,2)],
    [(0,1),(0,2),(0,3)],
    [(0,1),(1,0),(1,1)],
    [(0,1),(0,2),(1,2)],
    [(1,0),(2,0),(2,1)],
    [(0,1),(1,1),(1,2)],
    [(0,1),(1,1),(1,2)],
    [(1,0),(1,1),(2,1)],
]

dRow = [-1,0,1,0]
dCol = [0,-1,0,1]


def rotate_cw_90(vectors):
    result = []
    for vector in vectors:
        result.append((vector[1],-vector[0]))
    return result


max_value = -int(1e9)
for row in range(n):
    for col in range(m):
        for tetromino in tetrominoes:
            for _ in range(4):
                tetromino = rotate_cw_90(tetromino)
                sum_value = board[row][col]
                for vector in tetromino:
                    nRow,nCol = row+vector[0],col+vector[1]
                    if not (0 <= nRow < n and 0 <= nCol < m):
                        break
                    sum_value += board[nRow][nCol]
                else:
                    max_value = max(max_value,sum_value)

print(max_value)

풀이 2

DFS로 만들 수 없는 테트로미노와 DFS로 만들 수 있는 테트로미노를 따로 탐색해주면 된다.

문제를 풀던 중 나름 놀라운(?) 발견을 해냈는데, 행과 열 길이가 서로 다른 이차원 리스트를 90도 시계방향 회전할 때 다음과 같이 해도 된다는 것이다.

list(map(list,zip(*board[::-1])))

분명 처음 풀 때는 어려웠는데, 다시보니 그렇지도 않다는 생각이... 든다.

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

dRow = [-1,0,1,0]
dCol = [0,-1,0,1]
visited = [[0]*M for _ in range(N)]
tetromino = [
    [1,0],
    [1,1],
    [1,0]
]


def dfs(cnt,result,r,c):
    global answer
    if cnt >= 3:
        answer = max(answer,result)
        return
    for i in range(4):
        nr,nc = r+dRow[i],c+dCol[i]
        if 0 <= nr < N and 0 <= nc < M and visited[nr][nc] == 0:
            visited[nr][nc] = 1
            dfs(cnt+1,result+board[nr][nc],nr,nc)
            visited[nr][nc] = 0


answer = 0
# 'ㅏ' 모양을 제외한 테트로미노
for row in range(N):
    for col in range(M):
        visited[row][col] = 1
        dfs(0,board[row][col],row,col)
        visited[row][col] = 0
# 'ㅏ' 모양 테트로미노
for i in range(4):
    n,m = len(tetromino),len(tetromino[0])
    for r in range(N-n+1):
        for c in range(M-m+1):
            result = 0
            for row in range(n):
                for col in range(m):
                    if tetromino[row][col] == 1:
                        result += board[r+row][c+col]
            answer = max(answer,result)
    # 90도 시계방향 돌리기
    tetromino = list(map(list,zip(*tetromino[::-1])))


print(answer)