[baejoon] 백준 14500번 : 테트로미노 (by python 파이썬) BFS

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

14500번: 테트로미노

 

정답 code

#테트로미노
import sys
input = sys.stdin.readline

def dfs(r,c,bcount,total):
    global ans
    #종료조건1 - 최댓값에 못미치는 경우
    if ans >= total + max_value * (3-bcount):
        return
    #종료조건2 - 블럭 4개를 모두 활용한 경우
    if bcount == 4:
        ans = max(ans, total)
        return

    else :
        #상하좌우 방향 블럭 이어붙이기
        for i in range(4):
            nr = r + dr[i]
            nc = c + dc[i]
            #새좌표 유효범위와 탐색이력 확인
            if 0 <= nr < n and 0<= nc < m and visit[nr][nc] == 0:
                # ㅗ,ㅜ,ㅏ,ㅓ만들기 위해
                if bcount == 2: #현재 블럭이 2개가 놓인상태 
                    visit[nr][nc] = 1
                    #블럭 하나 추가후 기존블럭(현재 재귀 좌표)으로 돌아와 탐색재개(total값엔 새좌표의 값 추가)
                    dfs(r,c,bcount+1, total +paper[nr][nc]) 
                    visit[nr][nc] = 0
                visit[nr][nc] = 1
                dfs(nr,nc, bcount+1, total + paper[nr][nc])
                visit[nr][nc] = 0

n,m = map(int,input().split())
paper =[list(map(int,input().split())) for _ in range(n)]
visit = [[False]*m  for _ in range(n)]

dr = [-1,0,1,0]
dc = [0,1,0,-1]
ans = 0
max_value = max(map(max,paper))

for i in range(n):
    for j in range(m):
        visit[i][j] = 1
        dfs(i,j,1,paper[i][j])   #순차적 좌표 i,j 와 첫블럭이니 숫자 1, 현재 좌표속 값 입력
        visit[i][j] = 0

print(ans)

 

solution

처음엔 방법이 생각나지 않아 구글링을 해보니 BFS를 이용하여 푸신분도 있고 노가다코딩을 하신 분도 있었다.

나도 BFS를 이용하여 풀어보려하였는데 문제가 있었다.

 

다른 모양은 bfs를 호출하면 모든 모양을 탐색하는데,

ㅏ,ㅗ,ㅜ,ㅓ 모양은 불가능 한 것이였다.

블로그 몇개를 뒤져보니 해법이 있긴했는데 처음에 이해하기 굉장히 어려웠다.

 

가장 간단한 방법은 3번째 블럭을 붙이면서 재귀를 할때 좌표를 기존블럭으로 넣어주는것이다.

즉 세번째로 붙인 블럭이 아닌 두번째로 붙인 블럭으로 돌아와 다시 bfs를 실행하면 ㅏ,ㅗ,ㅓ,ㅜ 모양을 만들 수 있다.

 

재귀를 하면서 total값에 추가를 하기 때문에 3번째 블럭도 자동적으로 추가가 되며 전 블럭으로 돌아가 bfs를 수행한다.