[230116] 백준 14500번 - 테트로미노 (Python)

https://github.com/cjk09083/Code

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

14500번: 테트로미노

 

해답 1)

import sys
input=sys.stdin.readline

def getBox():
    board = []
    for _ in range(3):
        board.append([0]*(m+6))
    for _ in range(n):
        tmp = [0,0,0]
        tmp += list(map(int, input().split()))
        tmp += [0,0,0]
        board.append(tmp)
    for _ in range(3):
        board.append([0]*(m+6))

    return board

def sol(i,j):
    cnt = 0
    # 1 직선 (세로놓기)
    cnt = max(cnt, b[i][j] + b[i+1][j] + b[i+2][j] + b[i+3][j])
    # 2 직선 (가로놓기)
    cnt = max(cnt, b[i][j] + b[i][j+1] + b[i][j+2] + b[i][j+3])
    # 3 네모
    cnt = max(cnt, b[i][j] + b[i][j+1] + b[i+1][j+1] + b[i+1][j])
    # 4 ㄴ // 왼상단 시작 오른 하단 종료. (세로가 큰 ㄴ)
    cnt = max(cnt, b[i][j] + b[i+1][j] + b[i+2][j] + b[i+2][j+1])
    # 5 ㄴ // 오른 상단 시작 왼 하단 종료. (4 좌우 대칭)
    cnt = max(cnt, b[i][j+1] + b[i+1][j+1] + b[i+2][j+1] + b[i+2][j])
    # 6 ㄴ // 왼하단 시작 오른 상단 종료. (가로가 긴 ㄱ)
    cnt = max(cnt, b[i][j] + b[i][j+1] + b[i][j+2] + b[i+1][j+2])
    # 7 ㄴ // 왼하단 시작 오른 상단 종료. (6 대칭)
    cnt = max(cnt, b[i+1][j] + b[i][j] + b[i][j+1] + b[i][j+2])
    # 8 ㄴ // 왼상단 시작 오른 하단 종료. (세로가 긴 ㄱ)
    cnt = max(cnt, b[i][j] + b[i][j+1] + b[i+1][j+1] + b[i+2][j+1])
    # 9 ㄴ // 왼상단 시작 오른 하단 종료. (8 대칭)
    cnt = max(cnt, b[i][j+1] + b[i][j] + b[i+1][j] + b[i+2][j])
    # 10 ㄴ // 오른 상단 시작 왼 하단 종료 (가로가 긴 ㄴ)
    cnt = max(cnt, b[i][j] + b[i+1][j] + b[i+1][j+1] + b[i+1][j+2])
    # 11 ㄴ // 오른 상단 시작 왼 하단 종료 (10 대칭)
    cnt = max(cnt, b[i+1][j] + b[i+1][j+1] + b[i+1][j+2] + b[i][j+2])
    # 12 ㄴㄱ  // 왼 상단 시작 오른 하단 종료 (ㄴ 밑에 ㄱ)
    cnt = max(cnt, b[i][j] + b[i+1][j] + b[i+1][j+1] + b[i+2][j+1])
    # 13 ㄴㄱ  // 왼 하단 시작 오른 상단 종료 (ㄴ 밑에 ㄱ 좌우 반전)
    cnt = max(cnt, b[i][j+1] + b[i+1][j+1] + b[i+1][j] + b[i+2][j])
    # 14 ㄴㄱ  // 왼 상단 시작 오른 하단 종료 (ㄱ 우측에 ㄴ)
    cnt = max(cnt, b[i][j] + b[i][j+1] + b[i+1][j+1] + b[i+1][j+2])
    # 15 ㄴㄱ  // 오른 상단 시작 왼 하단 종료 (ㄱ 우측에 ㄴ 상하 반전)
    cnt = max(cnt, b[i+1][j] + b[i+1][j+1] + b[i][j+1] + b[i][j+2])
    # 16 ㅗ // ㅜ
    cnt = max(cnt, b[i][j] + b[i][j+1] + b[i+1][j+1] + b[i][j+2])
    # 17 ㅗ // ㅓ
    cnt = max(cnt, b[i][j+1] + b[i+1][j+1] + b[i+2][j+1] + b[i+1][j])
    # 18 ㅗ // ㅗ
    cnt = max(cnt, b[i+1][j] + b[i+1][j+1] + b[i][j+1] + b[i+1][j+2])
    # 19 ㅗ // ㅏ
    cnt = max(cnt, b[i][j] + b[i+1][j] + b[i+1][j+1] + b[i+2][j])

    return cnt

if __name__ == "__main__": 
    n, m = map(int,(input().split()))
    b = getBox()
    # print(*b, sep = "\n")
    result = 0

    for i in range(n):
        for j in range(m):
            result = max(result,sol(i+3,j+3))

    print(result)

- 주어진 board에서 가장자리에 0배열 3칸씩 추가

- 3,3 부터 n+3, m+3까지 변경하며 왼쪽위에서 시작하는 모든 도형의 경우의수 계산

- 경우의 수 중 가장 큰 값을 출력

- 1380ms

해답 2) 

import sys
input=sys.stdin.readline

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

def dfs(x,y,depth,res):
    global answer
    # 종료조건1) 탐색을 계속 진행하여도 최댓값에 못 미치는 경우
    if answer >= res + MAX*(4-depth):
        return

    # 종료조건2) 블록 4개를 모두 활용한 경우
    if depth==4:
        answer = max(answer, res)
        return

    # 상하좌우 방향으로 블록 이어 붙여 나가기
    for i in range(4):
        nx=x+dx[i] # 새로운 x 좌표
        ny=y+dy[i] # 새로운 y 좌표
        # 새로운 좌표가 유효한 범위 내 있고 탐색이력이 없는 경우
        if 0 <= nx < m and 0 <= ny < n and visit[ny][nx]==0:
            # 2번째 블록 연결 후 'ㅏ','ㅓ','ㅗ','ㅜ' 만들기
            if depth==2:
                visit[ny][nx]=1
                dfs(x,y,depth+1,res+board[ny][nx])
                visit[ny][nx]=0
            visit[ny][nx]=1
            dfs(nx,ny,depth+1,res+board[ny][nx])
            visit[ny][nx]=0

if __name__ == "__main__": 
    n,m=map(int,input().split())
    board=[list(map(int,input().split())) for _ in range(n)]
    answer,MAX = 0,max(map(max,board))
    visit=[[0]*m for _ in range(n)]

    for i in range(n):
        for j in range(m):
            visit[i][j]=1
            dfs(j,i,1,board[i][j])
            visit[i][j]=0

    print(answer)

- DFS를 사용해 탐색

- 172ms