[탐색/구현] 백준 14500 테트로미노 - 파이썬(Python)

 

[ Contents ]

 

 

1. 문제 (링크 참조)

14500번: 테트로미노

 

 

 

2. 문제 풀이

 테트릭스 모양으로 탐색한 뒤, 가장 점수를 출력하는 문제입니다.

 

2022.02.23 - [Algorithm] - [Algorithm] 깊이 우선 탐색(DFS), 끝까지 찾고 넘어가자

[Algorithm] 깊이 우선 탐색(DFS), 끝까지 찾고 넘어가자

 ㅗ모양을 제외하곤, DFS탐색으로 깊이 3까지만 탐색하면 모두 찾아낼 수 있습니다. 다만, ㅗ모양을 한 번 더 탐색해야 합니다.

 

 

 

3. 코드

import sys
from collections import deque
input = sys.stdin.readline

#입력
N, M = map(int, input().split())
tetromino = []
for _ in range(N):
    tetromino.append(list(map(int, input().split())))

#bfs 탐색: 시작지점(a,b), 남은 탐색횟수, 합계
def bfs(a, b, cnt, sum):
    print(a,b,cnt,sum)
    #남은 탐색횟수가 0이면 합계 반환
    if cnt == 0:
        return sum

    direction = [(1, 0), (-1, 0), (0, 1), (0, -1)]
    queue = deque([(a, b)])
    while queue:
        x, y = queue.popleft()
        for dx, dy in direction:
            nx, ny = x+dx, y+dy

            if 0 <= nx < N and 0 <= ny < M:
                queue.append((nx, ny))
                bfs(nx, ny, cnt-1, sum+tetromino[a][b])

res = 0
for i in range(N):
    for j in range(M):
        res = max(bfs(i, j, 3, 0), res)

print(res)

 본래 BFS탐색으로 깊이 3까지 탐색하면 ㅗ모양까지 다 찾을 수 있을거라 생각했습니다. 하지만 다시 빙빙 돌았고, visitied 테이블을 매번 초기화하기도 애매해서 포기했습니다.

 

 

import sys
input = sys.stdin.readline

#입력
N, M = map(int, input().split())
tetromino = []
for _ in range(N):
    tetromino.append(list(map(int, input().split())))

direction = [
    # ㅡ
    [(0, 0), (0, 1), (0, 2), (0, 3)], [(0, 0), (1, 0), (2, 0), (3, 0)],
    # ㅁ
    [(0, 0), (0, 1), (1, 0), (1, 1)],
    # L
    [(0, 0), (0, 1), (0, 2), (1, 0)], [(0, 0), (0, 1), (0, 2), (-1, 2)],
    [(0, 0), (1, 0), (1, 1), (1, 2)], [(0, 0), (0, 1), (0, 2), (1, 2)],
    [(0, 0), (1, 0), (2, 0), (2, 1)], [(0, 0), (1, 0), (2, 0), (2, -1)],
    [(0, 0), (0, 1), (1, 0), (2, 0)], [(0, 0), (0, 1), (1, 1), (2, 1)],
    # ㅗ
    [(0, 0), (0, 1), (0, 2), (1, 1)], [(0, 0), (0, 1), (0, 2), (-1, 1)],
    [(0, 0), (1, 0), (1, 1), (2, 0)], [(0, 0), (1, 0), (2, 0), (1, -1)],
    # ㄹ
    [(0, 0), (1, 0), (1, -1), (2, -1)], [(0, 0), (1, 0), (1, 1), (2, 1)],
    [(0, 0), (0, 1), (-1, 1), (-1, 2)], [(0, 0), (0, 1), (1, 1), (1, 2)]
]
res = 0
for x in range(N):
    for y in range(M):
        for direct in direction:
            sum = 0
            for dx, dy in direct:
                nx, ny = x+dx, y+dy
                if 0 <= nx < N and 0 <= ny < M:
                    sum += tetromino[nx][ny]
                else:
                    break
            res = max(sum, res)
print(res)

 그 대신에 테트리스 모양의 19가지 경우의 수를 그대로 탐색했습니다. 

 

 

[Python] 14500 - 테트로미노

 위 코드는 이 링크에서 아이디어를 얻어 작성했습니다.