알고리즘 공부/부르드포스

[백준] 14500번 테트로미노 - 파이썬

코딩 코딩 코오딩 2022. 4. 15. 15:12

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

 

14500번: 테트로미노

폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변

www.acmicpc.net

import sys

n,m = map(int,sys.stdin.readline().split())

graph = []
for i in range(n):
    graph.append(list(map(int,sys.stdin.readline().split())))

tetrominoes = [
    [(0,0), (0,1), (1,0), (1,1)], # ㅁ
    [(0,0), (0,1), (0,2), (0,3)], # ㅡ
    [(0,0), (1,0), (2,0), (3,0)], # ㅣ
    [(0,0), (0,1), (0,2), (1,0)],
    [(1,0), (1,1), (1,2), (0,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)],
    [(2,0), (2,1), (1,1), (0,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)], # ㅜ
    [(1,0), (1,1), (1,2), (0,1)], # ㅗ
    [(0,0), (1,0), (2,0), (1,1)], # ㅏ
    [(1,0), (0,1), (1,1), (2,1)], # ㅓ
    [(1,0), (2,0), (0,1), (1,1)],
    [(0,0), (1,0), (1,1), (2,1)],
    [(1,0), (0,1), (1,1), (0,2)],
    [(0,0), (0,1), (1,1), (1,2)]
]


answer = 0
for tetromino in tetrominoes:
    for x in range(n):
        for y in range(m):
            temp = 0
            for i in range(4):
                a = tetromino[i][0] + x
                b = tetromino[i][1] + y
                if 0 <= a < n and  0 <= b < m:
                    temp += graph[a][b]
                else:
                    break
            answer = max(answer,temp)
print(answer)

문제를 엄청 생각했는데 결국 못풀을거 같아서 다른분 풀이를 참고했다

https://jeongchul.tistory.com/670

 

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

백준 삼성 코딩 기출 문제 - 테트로미노 python 출처 : BAEKJOON ONLINE JUDGE 2048 (Easy) (https://www.acmicpc.net/problem/14500) 문제 설명 문제는 흔히 우리가 알고 있는 테트리스의 모양을 이용해서 주어진..

jeongchul.tistory.com

tetrominoes = [
    [(0,0), (0,1), (1,0), (1,1)], # ㅁ
    [(0,0), (0,1), (0,2), (0,3)], # ㅡ
    [(0,0), (1,0), (2,0), (3,0)], # ㅣ
    [(0,0), (0,1), (0,2), (1,0)],
    [(1,0), (1,1), (1,2), (0,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)],
    [(2,0), (2,1), (1,1), (0,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)], # ㅜ
    [(1,0), (1,1), (1,2), (0,1)], # ㅗ
    [(0,0), (1,0), (2,0), (1,1)], # ㅏ
    [(1,0), (0,1), (1,1), (2,1)], # ㅓ
    [(1,0), (2,0), (0,1), (1,1)],
    [(0,0), (1,0), (1,1), (2,1)],
    [(1,0), (0,1), (1,1), (0,2)],
    [(0,0), (0,1), (1,1), (1,2)]
]

이분 풀이에서 이거만 참고했는데 약간 충격을 먹었다

실제 시험에서 정말 모를때 이렇게라도 해야겠다는 생각을 했다

dfs나 다른 방법도 존재하는 거 같은데 그건 나중에 한번 생각해봐야겠다

부르드포스 알고리즘을 이용하는 문제이니 너무 깊게 생각할 필요는 없는거 같다

 

이런 방식을 적용하기 위해서는  조건이 한정적인가? 부터 따져보고 하면 될거같다

 

 

반응형