[BOJ 백준, 삼성 SW 역량 테스트 기출 문제] 14500번 : 테트로미노 (Python, 파이썬)

www.acmicpc.net/problem/14500

14500번: 테트로미노

 

문제를 잘 읽자!

문제를 잘 못 읽어서 1시간을 고민하다가 질문검색을 통해 코드를 보고 문제를 잘못 읽은것을 깨달았다.

 

테트로미노 "하나"를 적절히 놓아서 테트로미노가 놓인 칸에 쓰여 있는 수들의 합을 최대로 하는 프로그램을 작성하시오.

 

주어진 종이에 여러 종류의 테트로미노를 놓고 그 중에 최대를 구하는 것이 아니다. 

최대 500x500 크기의 종이에 테트로미노 1개를 놓고 놓인 부분의 합이 최대가 되는 것을 구하는 문제이다. 

 

 

처음에는 어떻게 접근해야할 지 감이 잘 오지않아서 5개 블록에 대한 모양을 전부 입력해서 넣었다.

하지만, 뭔가 이 방법은 아닌것 같아서 좀 더 고민해보고 질문 게시판을 찾아보다가 블록을 정할 때 단순히 4방 탐색으로구할 수 있다는 것을 알았다.

 

 

4방향 탐색이면 대략 아래와 같은 형태로 진행이 되는데, 단순히 상하좌우를 탐색한다고 5가지 블록모양 및 각 블록이 회전하는 것에 대한 모든 경우를 다 탐색하는 것을 이해하지 못했다.

dy = [0,0,1,-1]
dx = [1,-1,0,0]
.
.
for i in range(4):
        ny = y + dy[i]
        nx = x + dx[i]
        if 0<=ny and ny<n and 0<=nx and nx<m and not visited[ny][nx]:
            visited[ny][nx] = True
            result = max(result, board[y][x] + dfs(ny, nx, count+1))
        .
        .
        .

 

 

좀 더 고민을 하다보니 다음과 같은 사실을 알았다.

• 모든 블록은 4개의 칸으로 구성되어 있다
• 하나의 기준점을 잡고 깊이우선탐색(DFS)로 4번을 들어가면 해당 블록 모양에 맞게 탐색 할 수 있다.

 

꼭 블록의 모양을 고정적으로 선언해주지 않더라도 범위를 벗어나지 않고, 인접한 4개의 칸에 대해 4번의 DFS가 이루어지면 "ㅗ"를 제외한 모든 블록 모양을 만들 수 있는 것이다.

 

 

역시 재귀는 어려운 것 같다..

 

소스코드

 

import sys
n, m = map(int, input().split())

board = [list(map(int, input().split())) for _ in range(n)]
visited = [[False]*m for _ in range(n)]
answer = -1

dy = [0,0,1,-1]
dx = [1,-1,0,0]

def fuck_block(y, x):
    result = 0 
    #ㅗ (현재 좌표 ㅡ의 가운데)
    if y >= 1 and x >= 1 and x < m - 1:
        result = max(result, board[y][x - 1] + board[y][x] + board[y - 1][x] + board[y][x + 1]) 
    #ㅏ (현재 좌표 ㅣ의 가운데)
    if y >= 1 and y < n - 1 and x < m - 1:
        result = max(result, board[y - 1][x] + board[y][x] + board[y][x + 1] + board[y + 1][x]) 
    #ㅜ (현재 좌표 ㅡ의 가운데)
    if y >= 0 and y < n - 1 and x < m - 1:
        result = max(result, board[y][x - 1] + board[y][x] + board[y + 1][x] + board[y][x + 1]) 
    #ㅓ (현재 좌표 ㅣ의 가운데)
    if y >= 1 and y < n - 1 and x >= 1:
        result = max(result, board[y - 1][x] + board[y][x] + board[y][x - 1] + board[y + 1][x]) 

    return result

def dfs(y, x, count):       
    if count == 4: # 4개의 칸을 다 갔으면
        return board[y][x]
    result = 0
    for i in range(4):
        ny = y + dy[i]
        nx = x + dx[i]
        if 0<=ny and ny<n and 0<=nx and nx<m and not visited[ny][nx]:
            visited[ny][nx] = True
            result = max(result, board[y][x] + dfs(ny, nx, count+1))
            visited[ny][nx] = False      
    return result
    
for i in range(n):
    for j in range(m):
        visited[i][j] = True
        answer= max(answer, dfs(i, j, 1))
        answer = max(answer, fuck_block(i, j))
        visited[i][j] = False
print(answer)