[python] 백준 14500번 : 테트로미노 (backtracking)

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

14500번: 테트로미노

정답 코드)

def dfs(r, c, idx, total):
    global ans
    if ans >= total + max_val * (3 - idx):
        return
    if idx == 3:
        ans = max(ans, total)
        return
    else:
        for nr, nc in move:
            nr += r; nc += c
            if 0 <= nr < N and 0 <= nc < M and visit[nr][nc] == 0:
                if idx == 1:
                    visit[nr][nc] = 1
                    dfs(r, c, idx + 1, total + arr[nr][nc])
                    visit[nr][nc] = 0
                visit[nr][nc] = 1
                dfs(nr, nc, idx + 1, total + arr[nr][nc])
                visit[nr][nc] = 0


N, M = map(int, input().split())
arr = [list(map(int, input().split())) for _ in range(N)]
visit = [([0] * M) for _ in range(N)]
move = [(1, 0),(0, 1),(-1, 0),(0, -1)]
ans = 0
# 이중 배열의 최댓값 val 구하기
max_val = max(map(max, arr))

for r in range(N):
    for c in range(M):
        visit[r][c] = 1
        dfs(r, c, 0, arr[r][c])
        visit[r][c] = 0

print(ans)

idx = 1일 때 새로운 블럭이 아닌 기존 블럭에서 탐색하게 만들면 ㅗ, ㅜ, ㅓ, ㅏ 모양을 만들 수 있다. 

종이(2차원배열)에서 최대값을 찾아서 max(map(max, arr))
선택할 수 있는 남은 블럭의 갯수만큼 (3 - idx) 곱해주고
현재 누적합 total 에 더해서 ans와 비교해주는 방식으로 가지치기 가능

 

또 다른 풀이)

import sys
input = sys.stdin.readline

# 상, 하, 좌, 우
move = [(0, 1), (0, -1), (1, 0), (-1, 0)]

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

# 최대값 변수
maxValue = 0

# ㅗ, ㅜ, ㅓ, ㅏ 제외한 모양들 최대값 계산
def dfs(i, j, dsum, cnt):
    global maxValue
    # 모양 완성되었을 때 최대값 계산
    if cnt == 4:
        maxValue = max(maxValue, dsum)
        return

    # 상, 하, 좌, 우로 이동
    for n in range(4):
        ni = i+move[n][0]
        nj = j+move[n][1]
        if 0 <= ni < N and 0 <= nj < M and not visited[ni][nj]:
            # 방문 표시 및 제거
            visited[ni][nj] = True
            dfs(ni, nj, dsum + board[ni][nj], cnt+1)
            visited[ni][nj] = False


# ㅗ, ㅜ, ㅓ, ㅏ 모양의 최대값 계산
def exce(i, j):
    global maxValue
    for n in range(4):
        # 초기값은 시작지점의 값으로 지정
        tmp = board[i][j]
        for k in range(3):
            # move 배열의 요소를 3개씩 사용할 수 있도록 인덱스 계산
            # 012, 123, 230, 301
            t = (n+k)%4
            ni = i+move[t][0]
            nj = j+move[t][1]

            if not (0 <= ni < N and 0 <= nj < M):
                tmp = 0
                break
            tmp += board[ni][nj]
        # 최대값 계산
        maxValue = max(maxValue, tmp)


for i in range(N):
    for j in range(M):
        # 시작점 visited 표시
        visited[i][j] = True
        dfs(i, j, board[i][j], 1)
        visited[i][j] = False

        exce(i, j)

print(maxValue)

ㅓ, ㅏ, ㅗ, ㅜ를 처리하기 위해 exec 함수 구현 

이때 move 방향 중 3방향에만 접근하기 위해 t = (n+k)%4 개념 사용

 

틀린 코드)

n, m = map(int, input().split())
maps = []
move = [(1,0), (0,1), (-1,0), (0,-1)]
max_val = 1


def implementations(x, y, count):
    global total, visited
    total += maps[x][y]
    visited[x][y] = True
    # 테트로미노가 완성되었다면
    if count == 4:
        return
    val = 0
    next_x, next_y = -1, -1
    for xx, yy in move:
        nx, ny = xx + x, yy + y
        if 0 <= nx < n and 0 <= ny < m:
            if val < maps[nx][ny] and not visited[nx][ny]:
                val = maps[nx][ny]
                next_x, next_y = nx, ny
    implementations(next_x, next_y, count+1)


for i in range(n):
    tmp = list(map(int, input().split()))
    max_val = max(max_val, max(tmp))
    maps.append(tmp)

result = 0
for i in range(n):
    for j in range(m):
        if maps[i][j] == max_val:
            total = 0
            visited = [[False]*m for _ in range(n)]
            implementations(i, j, 1)
            result = max(total, result)

print(result)

반례) 

테스트 케이스 3번 

4 10
1 2 1 2 1 2 1 2 1 2
2 1 2 1 2 1 2 1 2 1
1 2 1 2 1 2 1 2 1 2
2 1 2 1 2 1 2 1 2 1

틀린 이유1)

가장 큰 value의 좌표 목록을 리스트로 구한 뒤 

value의 상 하 좌 우 방향으로 가장 큰 값을 더하는 그리디 방식으로 문제를 구현하였다. 그리고 나서 보니 반례 3번에 대한 케이스 같은 경우는 2에서 상하 좌우로 이동할때 가장 큰 값은 1뿐이다.

2 1 2

  2

이 케이스에서는 다음과 같은 값이 저장되어야 하므로 위 알고리즘은 틀렸다.

즉 dfs 구현을 사용하면 ㅗ, ㅜ, ㅓ, ㅏ 모양의 케이스는 처리가 불가능했다.

 

틀린 이유2)

그리디한 느낌으로 2차원 배열 map 내 원소 중 가장 큰 값(max_val)을 구하고 

큰 값이 나타나면 테트로미노를 만들어 최대값을 저장하는 방식을 사용했다.

하지만

0 0 0 6 0 0

0 0 0 0 0 0

0 0 0 0 0 0

0 0 0 0 0 0

1 2 3 5 4 1

다음과 같은 testcase가 input 값으로 들어온다면 최대값을 가지는 좌표에서 아무리 테트로미노를 만들어봐도 최대값을 갖기 못한다. 따라서 모든 좌표에 대해 테트리미노 값을 구하도록 접근하는 것이 맞다. 

항상 테스트 케이스를 잘 숙지하고 코드를 짜야한다는 사실을 잊지 말아야겠다. 잊지말자! 코딩테스트는 시간 싸움이다 !!! 

 

 

알게 된 사실)

이중 배열에서 최댓값 구하기 : max_val = max(map(max, arr))

좌표 네 개중 3개만 고르기 : 

for k in range(3):    d = (k+idx)%4

idx = 0일 때, d = 0, 1, 2

idx = 1일 때, d = 1, 2, 3

idx = 2일 때, d = 2, 3, 0

idx = 3일 때, d = 3, 0, 1

 

nx = x + move[d][0]

ny = y + move[d][1] -> 상하좌우 네 방향 중 세 방향만 접근 가능