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

분노의 테트리스..

머리가 나쁘면 몸이 고생한다

 

🌼 문제 링크

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

14500번: 테트로미노

• 티어: 골드 IV
• 분류: 구현, 브루트포스 알고리즘

 

 

❗ TRIAL 1.

코드

import sys
input = sys.stdin.readline

from collections import deque

N, M = list(map(int, input().split()))
paper = []
totalmax = 0
for _ in range(N):
    line = list(map(int, input().split()))
    paper.append(line)
    totalmax = max(totalmax, max(line))

def solution(init_i, init_j, N, M):
    maxval = 0
    
    dis = [1, -1, 0, 0]
    djs = [0, 0, 1, -1]
    
    queue = deque([([(init_i, init_j)], paper[init_i][init_j])])
    while queue:
        path, ctr = queue.popleft()
        i, j = path[-1]
        for di, dj in zip(dis, djs):
            new_i, new_j = i+di, j+dj
            if 0<=new_i<N and 0<=new_j<M and (new_i, new_j) not in path:
                new_path, new_val = path+[(new_i, new_j)], val+paper[new_i][new_j]
                if len(path) == 3:
                    maxval = max(maxval, new_val)
                else:
                    queue.append((new_path, new_val))

    T_shapes = [
        [(0, -1), (0, 1), (1, 0)], #ㅏ
        [(0, -1), (0, 1), (-1, 0)], #ㅓ
        [(-1, 0), (1, 0), (0, 1)], #ㅜ
        [(-1, 0), (1, 0), (0, -1)], #ㅗ
    ]

    for center_di, center_dj in zip(dis+[0], djs+[0]):
        center_i, center_j = init_i+center_di, init_j+center_dj
        if 0<=center_i<N and 0<=center_j<M:
            center_val = paper[center_i][center_j]
            for T_d in T_ds:
                T_sum = center_val
                for di, dj in T_d:
                    adj_i, adj_j = center_i+di, center_j+dj
                    if not (0<=adj_i<N and 0<=adj_j<M):
                        break
                    T_sum += paper[adj_i][adj_j]
                maxval = max(maxval, T_sum)
    
    return maxval
                    
maxval = totalmax+3
for i in range(N):
    for j in range(M):
        if paper[i][j]*4 > maxval:
            maxval = max(maxval, solution(i, j, N, M))

print(maxval)

 

코드 설명

 

- 우선 모든 포인트에 대해 검사하지는 않고, 현재 포인트 값 * 4 > 현재 최댓값 인 경우에만 검사를 진행했다. 총 검사 횟수를 줄이기 위함.

- 초기 최댓값을 구하기 위해 입력받은 값들에 대해 최대값을 구하고, 거기에 3을 더한 값을 초기 최댓값으로 설정했다. (모든 값이 자연수라는 조건이 있으므로)

- T자를 제외한 나머지는 BFS로 구하고, T자는 따로 빼서 구함

 

틀린 원인

 

틀림. T자에서  가운데가 최댓값이 아닌 경우를 지나침

반례:

4 4 
1 1 1 1
1 2 1 1
1 2 9 1
1 2 1 1

 

 

❗ TRIAL 2.

코드

import sys
input = sys.stdin.readline

from collections import deque

N, M = list(map(int, input().split()))
paper = []
totalmax = 0
for _ in range(N):
    line = list(map(int, input().split()))
    paper.append(line)
    totalmax = max(totalmax, max(line))

def solution_BFS(init_i, init_j, N, M):
    maxval = 0
    
    dis = [1, -1, 0, 0]
    djs = [0, 0, 1, -1]
    
    queue = deque([( [(init_i, init_j)], paper[init_i][init_j] )]) #path, val
    
    while queue:
        path, val = queue.popleft()
        i, j = path[-1]
        for di, dj in zip(dis, djs):
            new_i, new_j = i+di, j+dj
            if 0<=new_i<N and 0<=new_j<M and (new_i, new_j) not in path:
                new_path, new_val = path+[(new_i, new_j)], val+paper[new_i][new_j]
                if len(new_path) == 4:
                    maxval = max(maxval, new_val)
                else:
                    queue.append((new_path, new_val))

    return maxval

def solution_T(init_i, init_j, N, M):
    maxval = 0

    T_shapes = [
        [(0, -1), (0, 1), (1, 0)], #ㅏ
        [(0, -1), (0, 1), (-1, 0)], #ㅓ
        [(-1, 0), (1, 0), (0, 1)], #ㅜ
        [(-1, 0), (1, 0), (0, -1)], #ㅗ
    ]

    dis = [1, -1, 0, 0]
    djs = [0, 0, 1, -1]
    
    for center_di, center_dj in zip(dis+[0], djs+[0]):
        center_i, center_j = init_i+center_di, init_j+center_dj
        if 0<=center_i<N and 0<=center_j<M:
            center_val = paper[center_i][center_j]
            for T_adj in T_shapes:
                T_val = center_val
                for di, dj in T_adj:
                    adj_i, adj_j = center_i+di, center_j+dj
                    if not (0<=adj_i<N and 0<=adj_j<M):
                        break
                    T_val += paper[adj_i][adj_j]
                maxval = max(maxval, T_val)
                
    return maxval
                    
maxval = totalmax+3
for i in range(N):
    for j in range(M):
        if paper[i][j]*4 > maxval:
            maxval = max(maxval, solution_BFS(i, j, N, M), solution_T(i, j, N, M))
print(maxval)

 

수정한 부분

 

- 일단 BFS 부분과 T 부분의 코드를 분리.

- T 부분만 수정했음.

- init_i, init_j를 포함하는 T자형태만 검사할까 하다가 도저히 코드를 못짜겠어서 그냥 init_i, init_j 포함 상하좌우 좌표에 대해 T자를 검사하는 코드를 추가

 

틀린 원인

 

틀림. BFS로 탐색하는 T자가 아닌 다른 모양에서도 맨 끝이 아닌 부분에 최댓값이 위치할 수도 있다..

반례:

4 4
1 2 1 1
1 9 1 1
1 2 1 1
1 2 1 1

검사하는 포인트의 상하좌우에 대해 동일한 검사하는 코드를 추가해야 하나 했는데

그렇게 하면 중복으로 검사하는 경우가 너무 많아짐

 

💡 Solution

코드

import sys
input = sys.stdin.readline

from collections import deque

N, M = list(map(int, input().split()))
paper = []
totalmax = 0
for _ in range(N):
    line = list(map(int, input().split()))
    paper.append(line)
    totalmax = max(totalmax, max(line))

def solution_BFS(init_i, init_j, N, M):
    maxval = 0
    
    dis = [1, -1, 0, 0]
    djs = [0, 0, 1, -1]
    
    queue = deque([( [(init_i, init_j)], paper[init_i][init_j] )]) #path, val
    
    while queue:
        path, val = queue.popleft()
        for i, j in path:
            for di, dj in zip(dis, djs):
                new_i, new_j = i+di, j+dj
                if 0<=new_i<N and 0<=new_j<M and (new_i, new_j) not in path:
                    new_path, new_val = path+[(new_i, new_j)], val+paper[new_i][new_j]
                    if len(new_path) == 4:
                        maxval = max(maxval, new_val)
                    else:
                        queue.append((new_path, new_val))

    return maxval
       
maxval = totalmax+3
for i in range(N):
    for j in range(M):
        if paper[i][j]*4 > maxval:
            maxval = max(maxval, solution_BFS(i, j, N, M))
print(maxval)

 

코드 설명

• 모든 포인트에 대해 검사하지는 않고, 현재 포인트 값 * 4 > 현재 최댓값 인 경우에만 검사를 진행 (총 검사 횟수를 줄이기 위함)
• 초기 최댓값을 구하기 위해 입력받은 값들에 대해 최대값을 구하고, 거기에 3을 더한 값을 초기 최댓값으로 설정했다. (모든 값이 자연수라는 조건이 있으므로)
• BFS를 이용해 모든 모형을 구함.
  • 현재위치에서 시작해서, 상하좌우 인접한 좌표로 이동후 path를 누적해서 queue에 저장한다. 이 때 path에 속하는 값들의 합도 함께 저장한다 (val)
  • queue에서 pop을 해서 path를 얻은 후, path에 속하는 모든 포인트에 대해 상하좌우 인접한 좌표로 이동을 반복한다. 이 때, 이동할 좌표가 이미 path에 있으면 이동하지 않는다.
  • path의 길이가 4가 되면 더이상 queue에 append하지 않고, maxval과 비교해서 가장 큰 값을 찾는다.
  • 이렇게 하면 T자를 따로 분리하지 않아도 됨.

 

결과

• Solution의 코드 - 384ms
• Solution의 코드로 모든 point 검사 시 - 시간초과
• Trial3의 코드로 모든 point 검사 시 - 2720ms

 

다른 풀이

• 풀이1: DFS 이용 (188ms)
  • 모든 포인트에 대해 검사. 단, 매 depth마다, 남은 depth*최대값을 더해도 현재 최대값보다 작은 경우 탐색을 중지함으로써 탐색 횟수를 줄임 (이 방식으로 포인트를 걸러내는게 시간을 더 줄일 수 있는 듯 하다.)
  • 한 포인트 -> 인접 포인트 -> 인접 포인트 이렇게 depth가 4가 될 때까지 진행
  • T모양에 대해 검사하기 위해, depth가 2인 경우에는 이전 위치에서 이어서 진행하도록 함
    • 예) (x, y) -> (x, y+1) -> (x, y+2) -> (x+1, y+1)