백준 - [Gold 5] 14500번 테트로미노

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

14500번: 테트로미노

삼성 기출로 나왔던 문제입니다.

---

문제 설명

- N, M: 맵의 높이, 넓이

- 테트로미노: 정사각형 4개를 이어붙인 모양 

테트로미노

- 테트로미노 하나를 적절히 놓아서 테트로미노가 놓인 칸에 쓰여 있는 수들의 합을 최대

- 테트로미노들은 회전 대칭 가능

---

풀이

이 문제 같은 경우는 도형이 5개에다가 회전을 해도 총 경우의 수가 15가지 ex) ㅜ ㅏ ㅗ ㅓ (4가지) 가 나옵다. 각 지점마다 해당 경우를 대응해서 정답을 수하는 코드가 대부분이였습니다. 속도의 측면에서는 이러한 방식이 뛰어나지만 모든 경우의 수를 일일이 디버깅하기는 힘든 노릇이라 DFS 백트래킹으로 한번 구현해보았습니다.

백트래킹(Back Tracking)
- 완전 탐색에서 불필요한 분기(Branch)를 가지치기(Pruning)
- 해를 찾는 도중 해가 아니어서 막히면, 되돌아가서 다시 해를 찾아가는 기법

- DFS + 백트래킹

- dfs중 방문 체크 / 해제를 해줘야 됨

- dfs 종료조건: 길이가 4이상일 때

- 'ㅜ' 모양 같은 경우는 dfs로 체크할 수 없는 모양이라 따로 예외로 체크

   'ㄱ'이나 'ㅡ'모양은 만들 수 있는데 스택으로 생각해보면 'ㅜ' 모양은 불가능합니다.

 

코드

def dfs(x, y, value, length):
    
    global answer

    # dfs 종료 조건
    if length >= 4:
        answer = max(answer, value)
        return
    
    # 4방향 체크
    for d in direction:
        nx = x + d[0]
        ny = y + d[1]
        if 0 <= nx < N and 0 <= ny < M and not visit[nx][ny]:

            visit[nx][ny] = True # 방문 체크

            # 다음지점 value 더하고 length 더해서 호출
            dfs(nx, ny, value+MAP[nx][ny], length+1)

            visit[nx][ny] = False # 방문 체크 해제

def exception_check(x, y, value):

    global answer
    # ㅏ ㅜ ㅓ ㅗ 순으로 체크 0,0
    # 점은 가장 1. 왼쪽 2. 상단에 있다고 판단.
    if 0 <= x+2 < N and 0 <= y+1 < M: # ㅏ
        value = MAP[x][y] + MAP[x+1][y] + MAP[x+2][y] + MAP[x+1][y+1]
        answer = max(answer, value)

    if 0 <= x+1 < N and 0 <= y+2 < M: # ㅜ
        value = MAP[x][y] + MAP[x][y+1] + MAP[x][y+2] + MAP[x+1][y+1]
        answer = max(answer, value)
    
    if 0 <= x-1 and x+1 < N and 0 <= y+1 < M: # ㅓ
        value = MAP[x][y] + MAP[x-1][y+1] + MAP[x][y+1] + MAP[x+1][y+1]
        answer = max(answer, value)

    if 0 <= x-1 and 0 <= y+2 < M: # ㅗ
        value = MAP[x][y] + MAP[x][y+1] + MAP[x][y+2] + MAP[x-1][y+1]
        answer = max(answer, value)


from sys import stdin
stdin = open("input.txt", "r")
# 입력
N, M = map(int, stdin.readline().split())
MAP = [list(map(int, stdin.readline().split())) for _ in range(N)]

direction = ((-1, 0), (1, 0), (0, -1), (0, 1)) # ^ > v < 순
visit = [[False] * M for _ in range(N)]
answer = 0

for i in range(N):
    for j in range(M):

        # 시작지점도 방문 체크 해제 필요
        visit[i][j] = True

        dfs(i, j, MAP[i][j], 1)

        visit[i][j] = False

        # ㅜ 모양의 경우 dfs로 체크가 불가능해서 따로 처리.
        exception_check(i, j, MAP[i][j])

print(answer)

exception_check처럼 모든 경우의 수를 구현해 놓아도 문제는 풀립니다! 감사합니다.

 

코드: https://github.com/smothly/Algorithm_Solving/blob/master/boj-14500.py