[삼성 SW 역량테스트 기출] 백준 14500번 테트로미노(Python)

문제 링크 : https://www.acmicpc.net/problem/14500]

난이도 : 골드 4

14500번: 테트로미노

 

문제

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

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

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

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

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

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

입력

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

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

출력

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

 

---

📌 풀이 1 ) 완전 탐색

숨 참고 구현 DIVE~ 

오랜만에 빡구현 문제 .. 머리가 아프다 ^ ㅠ ^ 

 

이제 이런 문제만 보면 완탐 밖에 방법이 없는 것 같아보인다.. 

 

완탐을 쓰려면 가장 중요한 것은 시간 복잡도!

 

이 문제에서 완전탐색을 하려면 모든 좌표를 순회하면서 가능한 블럭 모양(회전, 대칭 포함해서)을 모두 대어보고 계산해서 그 중 최댓값을 구해내는 것이다. 

 

최악의 경우, 500x500의 맵의 크기를 가졌을 때이다, 

즉, 500 x 500 x 5 (블럭의 종류) x 4 (회전 개수) x 4 (대칭 개수) = 대략 25 x 10^6 으로 제한 시간 2초 안에 풀 수 있는 문제이다.

 

나능 완탐으로 푸려다가 너무 코드가 꼬여버려서 실패했다,, ㅠㅠ

 

문제 해결 과정을 차근차근 보면, 

 

[입력] 

맵의 크기(N,M), 맵의 정보 (arr)

 

[중간 과정] 

1. 각 블럭 모양에 대한 좌표를 저장한다.

-> 블럭 모양을 담은 좌표에 대한 리스트 필요

 

2. 모든 점을 순회하면서 블럭 모양 리스트에서 하나씩 꺼내 그 좌표에 해당하는 값들을 더해준다. 

-> 연산시, 범위 벗어나지 않는지 체크 필요

 

3. max() 를 사용하여 나오는 결과값마다 값을 비교해서 ans 를 갱신한다.

 

[출력]

가장 큰 ans 를 출력한다.

 

블록의 가능한 패턴에 대한 좌표는 다음처럼 나타낼 수 있다.

 

 

 

 

과정은 간단하지만, 코드를 작성하면서 실수하지 않는게 중요한 것 같다. (정신 완전 차려야댐..)

구현이 진짜 어려운게 어떻게 풀지는 알겠는데,,

막상 코드로 작성하려니까 어떤 순서로 풀어내야할지 막막?하다 ㅠ ㅅ ㅠ

실제 시험에서 좌표 값 하나 잘못 입력하면 멘탈 와르르창창일듯

 

그리고 블럭 내의 값들을 계산하는 함수를 새로 만들었는데,

이 함수에서 해당 좌표들의 범위가 맵을 벗어나지 않는지 꼭! 체크를 해줘야한다.

 

📌 완전 탐색 정답 코드

시간 : 604ms

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

arr = [list(map(int, input().split())) for _ in range (N)]


# 가능한 모든 테트로미노 모양
tets = [[(0,1), (0,2), (0,3)], [(1,0), (2,0), (3,0)], # 1x4 형태 
        [(0,1), (1,0), (1,1)], # 2x2형태
        [(1,0),(1,1),(2,1)], [(0,-1), (1,-1), (1,-2)], # ㄹ자 (회전)
        [(1,0), (1,-1), (2,-1)],[(0,1), (1,1), (1,2)], # ㄹ자 (대칭)
        [(1,0), (2,0), (2,1)], [(0,1), (0,2), (1,0)], # ㄴ자 (회전)
        [(0,1),(1,1), (2,1)], [(0,1), (0,2), (-1,2)],
        [(1,0),(2,0),(2,-1)],[(0,1),(0,2),(1,2)], # ㄴ자 (대칭)
        [(1,0),(2,0),(0,1)], [(1,0),(1,1),(1,2)],
        [(1,0),(1,1),(1,-1)], [(1,0),(1,1),(2,0)], # ㅗ자(회전)
        [(0,-1),(1,0),(0,1)],[(0,1),(-1,1),(1,1)] 
]

def calc(i,j,tet) :
    temp = arr[i][j] # 시작 위치는 범위 내 유효한 값
    for di,dj in tet :
        # 나머지 위치에 대해서는 범위 내 유효한지 검사
        ni, nj = i + di, j + dj
        if 0 <= ni < N and 0<= nj < M :
            temp += arr[ni][nj]
        else :
            return 0
    return temp


ans = 0
for i in range (N) :
    for j in range (M) :
        for tet in tets:
            temp = calc(i,j,tet) # 현재 위치에서 가능한 모든 모양의 합 계산
            ans = max(temp, ans)

print(ans)

 

 

---

📌 풀이 2) DFS

 

4개의 블럭을 계속해서 뻗어나가며 값을 계산한다는 점에서 DFS/BFS 를 떠올려볼 수 있다. 

 

근데 BFS는 안된다!!!

왜냐 ,, ㅗ, ㅜ 모양의 블럭 때문이다.

다른 블럭들은 돌아올 필요 없이 한방향으로만 쭉 가서 ㄴ자, ㄹ자, ㅁ 모양을 만들어낼 수 있다. 

하지만 ㅗ, ㅜ 모양을 만들려면 이미 방문했던 블럭에 대해서 돌아와서 뻗어나가야한다. 

 

BFS는 인접한 위치에서 너비 우선 탐색을 하기 때문에 ㅗ, ㅜ 을 만들 수 없다. 

이말은 즉슨, 상하좌우로 재귀호출을 하는 기존의 DFS 방식으로도 풀 수가 없다.

 

ㅗ, ㅜ 를 만들 수 없는 이유를 그림으로 그려보면 더 이해하기 쉽다.

 

따라서 블럭을 붙인 새로운 위치에서 블럭 모양을 탐색하는 것이 아닌, 기존 위치에서 블럭을 탐색해야한다. (🫢 너무 어려워서 놀람)

그리고 백 트 래 킹 으로 상, 하, 좌, 우를 탐색하면 된다. 

 

앞에서 자주 풀었던 백트래킹 유형을 그대로 적용하면 되는 것!! 

트리 형태로 그려보면 다음과 같다.

 

 

 

 

이렇게 풀면 최악의 경우, 시간 복잡도는 500 x 500 x 4^3이 된다 !! 즉 이 방법으로도 문제를 해결할 수 있다.

 

근데 노가다 완탐이 더 쉬운 것 같애 ㅠㅠㅠㅠㅠㅠㅠㅠ

 

DFS 만 적용한 코드는 다음과 같다.

시간 : 1336 ms (DFS 라 시간이 더 걸린다.)

N, M = map(int, input().split())
arr = [list(map(int, input().split())) for _ in range (N)]

v= [[0] * M for _ in range (N)] # dfs 방문 표시 배열

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

def dfs(n, temp, lst) :
    global ans

    # 종료 조건
    if n == 4 :
        ans = max(temp, ans)
        return
    
    # 재귀 함수 호출 (자기 위치에서 뻣어나가기, 백트래킹)
    for cx, cy in lst :
        for i in range (4) :
            nx, ny = cx + dx[i], cy + dy[i]
            # 범위, 방문 검사
            if 0 <= nx < N and 0<= ny < M and v[nx][ny] == 0 :
                v[nx][ny] = 1
                dfs(n+1, temp + arr[nx][ny], lst + [(nx, ny)])
                v[nx][ny] = 0 # 방문표시 해제로 백트래킹


ans = 0

for i in range (N) :
    for j in range (M) :
        v[i][j] = 1
        dfs(1, arr[i][j], [(i,j)])

print(ans)

 

 

 

시간을 더 단축시켜보자.. 가지치기를 활용해서!!

사실 가지치기 유형 문제는 안 풀어봐서ㅠㅠ 이해하는데 너무 어려웠다.. 

 

일단 가지치기 스킬은 무조건 사용하는 것이 아니라

가능한 모든 경우에 대해 계산해보았는데 시간 초과가 난다면 활용할 수 있는 방법이다!

 

이 문제에서 매번 max값 비교를 하지 않고, ans 값이 갱신되지 않을 경우 가지를 쳐서 더 이상 탐색하지 않도록 하는 것이 훨씬 효율적일 것이다.

 

초기 맵의 max 값을 계산한 뒤, 만약 나머지 블럭 (4-n)개가 모두 max 값이어도 현재의 ans 값보다 크지 않다면,

싹 . 둑. 잘라버린다.

 

따라서 가지치기 조건을 식으로 나타내면 다음과 같다.

현재 블럭값 + (4 - n) * mx  <= ans 

 

📌 DFS & 가지치기 정답 코드 

시간 : 188ms (훨씬 단축!!)

N, M = map(int, input().split())
arr = [list(map(int, input().split())) for _ in range (N)]

v= [[0] * M for _ in range (N)] # dfs 방문 표시 배열

# 각 행에서 최대값을 찾은 뒤, 그 중 전체 배열의 최댓값을 찾음
mx = max(map(max, arr))

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

def dfs(n, temp, lst) :
    global ans

    # 가지치기
    if temp + (4-n) * mx <= ans : # 나머지 블럭이 모두 최댓값이어도 현재 ans 값보다 작다면 dfs 순회 정지
        return

    # 종료 조건
    if n == 4 :
        ans = max(temp, ans)
        return
    
    # 재귀 함수 호출 (자기 위치에서 뻗어나가기, 백트래킹)
    for cx, cy in lst :
        for i in range (4) :
            nx, ny = cx + dx[i], cy + dy[i]
            # 범위, 방문 검사
            if 0 <= nx < N and 0<= ny < M and v[nx][ny] == 0 :
                v[nx][ny] = 1
                dfs(n+1, temp + arr[nx][ny], lst + [(nx, ny)])
                v[nx][ny] = 0 # 방문표시 해제로 백트래킹

ans = 0
for i in range (N) :
    for j in range (M) :
        v[i][j] = 1
        dfs(1, arr[i][j], [(i,j)])

print(ans)

 

구현 + 백트래킹 + 가지치기 = ⚰️

 

✅ 오늘도 쉽지 않은 하루..