[Baekjoon] 14500번 : 테트로미노 (Python, 구현, 브루트포스, DFS, 백트래킹)

[Baekjoon] 14500번 : 테트로미노 (Python, 구현, 브루트포스, DFS, 백트래킹)

 

목차

 

 

 

 

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

14500번: 테트로미노

코드 링크

https://github.com/stellaluminary/Baekjoon

GitHub - stellaluminary/Baekjoon

 

Python

 

방법 1 - 메모리 37324KB / 시간 704ms / 코드 길이 1090B

 

본 문제는 브루트 포스를 이용하여 문제를 풀 수 있다.

그러나 여기서는 DFS를 통한 구현법에 대해 설명하고자 한다.

만약 브루트 포스와 관련된 내용을 원한다면 아래 링크 참조바란다.

 

https://jeongchul.tistory.com/670

백준 삼성 코딩 기출 문제 - 테트로미노 python

https://jshong1125.tistory.com/20

[백준/Python(파이썬)] 14500 테트로미노

 

ㅗ 모양을 제외하고는 dfs 4번에 걸쳐 최대값을 찾아낼 수 있다.

그러나 ㅗ는 위치적으로 dfs를 활용하기에 어렵다는 문제가 있다.

하여 별도로 구성해줘야 한다.

이에 adj라는 함수를 만들어 4방향에 대한 값들 중 최대가 되는 3개의 값을 반환하는 것으로 최대값을 구했다.

 

import sys
input = sys.stdin.readline

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

def dfs(x, y, step, tot):
    global n, m, ans, max_val

    if tot + max_val * (4 - step) <= ans:
        return

    if step == 4:
        ans = max(ans, tot)
        return

    for i in range(4):
        nx, ny = x+dx[i], y+dy[i]
        if 0 <= nx < n and 0 <= ny < m:
            if not visit[nx][ny]:
                visit[nx][ny] = 1
                dfs(nx, ny, step+1, tot+a[nx][ny])
                visit[nx][ny] = 0

def adj(x,y):
    global n, m, ans
    t = []
    for i in range(4):
        nx, ny = x+dx[i], y+dy[i]
        if 0 <= nx < n and 0 <= ny < m:
            t.append(a[nx][ny])
    if len(t) >= 3:
        tmp = a[x][y] + sum(sorted(t, reverse=True)[:3])
        ans = max(ans, tmp)

n,m = map(int, input().split())
a = [list(map(int, input().split())) for _ in range(n)]
visit = [[0] * m for _ in range(n)]
ans = 0
max_val = max(map(max, a))

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

print(ans)

 

방법 2 - 메모리 37316KB / 시간 260ms / 코드 길이 911B

 

방법 1에서 DFS 외 ㅗ를 위한 별도의 함수를 통해 구했지만 알아보니 다음과 같은 코드로 한 번에 구할 수 있다고 전해진다. 이 방법을 통해 최단 시간 내 주어진 코드가 문제의 조건에 부합하게 결과를 도출할 수 있다.

 

다만 설명을 조금 더 보충하자면 step==2일 때의 조건문이 추가된 이유는 말 그대로 ㅗ에 해당하는 모양 때문이다.

 

DFS라면 x와 y라는 초기 좌표를 기준으로 nx, ny를 재설정하여 dfs 재귀를 진행한다. 이 방법은 ㅗ를 제외한 나머지 모양에서는 통용되는 이야기이다.

 

그러나 ㅗ는 다르다.

 

아래 (0,0)에서 시작하는 dfs가 존재한다고 했을 때 2,0에서 1,1에 해당하는 곳을 갈 수 없다.

때문에 step 2에서는 nx, ny에 대한 값의 업데이트와 더불어 재귀되는 dfs 초기 x, y에 대해 nx, ny가 아닌 다시 제자리에서 재귀를 진행할 수 있도록 하는 것이다.

 

x,y = 1,0 & nx, ny = 2,0이기에 일반적으로는 nx, ny를 dfs의 초기 x, y로 설정 후 재귀를 진행해야하지만 step 2에서의 dfs(x=1, y=0, step+1=3, tot+a[nx][ny])로 설정함으로써 ㅗ 모양이 가능하게 한다는 의미

 

 

0,0
Step = 1: 1,0	Step = 3: 1,1
Step = 2: 2,0

  

import sys
input = sys.stdin.readline

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

def dfs(x, y, step, tot):
    global n, m, ans, max_val

    if tot + max_val * (4 - step) <= ans:
        return

    if step == 4:
        ans = max(ans, tot)
        return

    for i in range(4):
        nx, ny = x+dx[i], y+dy[i]
        if 0 <= nx < n and 0 <= ny < m and not visit[nx][ny]:
            if step == 2:
                visit[nx][ny] = 1
                dfs(x, y, step + 1, tot+a[nx][ny])
                visit[nx][ny] = 0
            visit[nx][ny] = 1
            dfs(nx, ny, step+1, tot+a[nx][ny])
            visit[nx][ny] = 0

n,m = map(int, input().split())
a = [list(map(int, input().split())) for _ in range(n)]
visit = [[0] * m for _ in range(n)]
ans = 0
max_val = max(map(max, a))

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