Baekjoon_14500_테트로미노

14500번: 테트로미노

 

문제

폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다.

• 정사각형은 서로 겹치면 안 된다.
• 도형은 모두 연결되어 있어야 한다.
• 정사각형의 변끼리 연결되어 있어야 한다. 즉, 꼭짓점과 꼭짓점만 맞닿아 있으면 안 된다.

정사각형 4개를 이어 붙인 폴리오미노는 테트로미노라고 하며, 다음과 같은 5가지가 있다.

아름이는 크기가 N×M인 종이 위에 테트로미노 하나를 놓으려고 한다. 종이는 1×1 크기의 칸으로 나누어져 있으며, 각각의 칸에는 정수가 하나 쓰여 있다.

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

테트로미노는 반드시 한 정사각형이 정확히 하나의 칸을 포함하도록 놓아야 하며, 회전이나 대칭을 시켜도 된다.

 

 

입력

첫째 줄에 종이의 세로 크기 N과 가로 크기 M이 주어진다. (4 ≤ N, M ≤ 500)

둘째 줄부터 N개의 줄에 종이에 쓰여 있는 수가 주어진다. i번째 줄의 j번째 수는 위에서부터 i번째 칸, 왼쪽에서부터 j번째 칸에 쓰여 있는 수이다. 입력으로 주어지는 수는 1,000을 넘지 않는 자연수이다.

 

 

출력

첫째 줄에 테트로미노가 놓인 칸에 쓰인 수들의 합의 최댓값을 출력한다.

 

 

 

해결방법

- 테트로미노가 놓여질 경우의 수는 시작점을 포함한 4개의 칸을 탐색하는 모든 경우의 수와 같다.

- DFS로 구현하였다.

 

문제 해결 1. 처음 작성했던 코드는 뽁큐 모양의 테트로미노를 탐색하지 못했다.

뽁큐 모양의 블럭은 이동하지 않고 제자리에서 나머지 3칸을 탐색한다.

아래의 그림은 시작점에서 오른쪽, 왼쪽, 아래쪽을 탐색한 것!

# 뽁큐 모양 탐색하기 위해서 제자리에서 3 방향 더 탐색하기
dfs(i, j, depth, midSum + board[ni][nj])

-> 이때 ni, nj 방문처리는 다른 방법과 같이 처리해주어야 함

 

 

문제 해결 2. pass는 했지만 시간이 너무 오래걸려서 백트래킹!

현재까지의 midSum에 아무리 큰 수가 더해지더라도 maxV 보다 작은 경우에는 유망하지 않다고 판단한다.

# 이차원 배열의 최대값 구하기 - 백트래킹
best = 0
for arr in board:
    best = max(max(arr), best)

# 백트래킹 - 아무리 큰 수가 앞으로 더해지더라도 maxV 보다 작은 경우에는 리턴
    if depth < 3:
        if maxV > midSum + best*(3-depth):
            return

 

 

 

정답 코드

def dfs(i, j, depth, midSum):
    global maxV

    # 백트래킹 - 아무리 큰 수가 앞으로 더해지더라도 maxV 보다 작은 경우에는 리턴
    if depth < 3:
        if maxV > midSum + best*(3-depth):
            return

    # 테트로미노 완성되었을 때
    if depth == 3:
        # 최대합 갱신해주기
        if midSum > maxV:
            maxV = midSum
    else:
        depth += 1
        for di, dj in [(0, 1), (1, 0), (-1, 0), (0, -1)]:
            ni, nj = i + di, j + dj
            if 0 <= ni < N and 0 <= nj < M and not visited[ni][nj]:
                # 방문처리 해주기
                visited[ni][nj] = 1

                # 뽁큐 모양 탐색하기 위해서 제자리에서 3 방향 더 탐색하기
                dfs(i, j, depth, midSum + board[ni][nj])

                # 뽁큐를 제외한 나머지 테트로미노 탐색
                dfs(ni, nj, depth, midSum + board[ni][nj])

                # 다음 탐색을 위해서 visited 원복 시켜주기
                visited[ni][nj] = 0
    return

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

board = [list(map(int, input().split())) for _ in range(N)]
visited = [[0]*M for _ in range(N)]

# 이차원 배열의 최대값 구하기 - 백트래킹
best = 0
for arr in board:
    best = max(max(arr), best)

maxV = 0
for i in range(N):
    for j in range(M):
        # 시작 인덱스 방문처리 해주기
        visited[i][j] = 1
        # 처음 midSum 값은 시작인덱스의 값
        dfs(i, j, 0, board[i][j])
        visited[i][j] = 0

print(maxV)