[삼성SW역량][Python/BOJ] 백준 14500 테트로미노(DFS)

 

 

728x90

 

 

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

14500번: 테트로미노

 

 

주어진 mp를 돌면서 4개로 연결된 폴리오미노의 합중 가장 큰 합을 구해 출력하면 된다. 

 

시간 초과를 막는 방법 : 가장 큰 값을 구해서 (가장 큰값 * (3-idx) ) + val 이 현재 답보다 작거나 같다면 return 한다. 

'ㅗ'의 경우는 dfs로 찾을 수 없으므로 

if idx ==1 : 을 따로 코드를 만들어 주어야한다. 

 

 

 

 

 

코드 : 

 

n,m = map(int,input().split())
mp = [list(map(int,input().split())) for _ in range(n)]
vis = [[0]*m for i in range(n)]
dx = [-1,0,1,0]
dy = [0,1,0,-1]
ans = 0
max_val = max(map(max,mp))


def dfs(i,j,idx,total) :
    global ans
    if ans >= total + max_val * (3-idx) :
        return 
    if idx == 3 :
        ans = max(ans,total)
        return 
    else :
        for k in range(4) :
            nx = i + dx[k]
            ny = j + dy[k]
            if 0<=nx<n and 0<=ny<m and vis[nx][ny]==0 :
                if idx == 1 : # 'ㅗ'모양을 위해  # ㅗ은 연달아 이을수 없다.
                    vis[nx][ny] = 1
                    dfs(i,j,idx+1, total + mp[nx][ny])
                    vis[nx][ny] = 0
                vis[nx][ny] = 1
                dfs(nx,ny,idx+1, total+mp[nx][ny])
                vis[nx][ny] = 0
                    

for i in range(n) :
    for j in range(m) :
        vis[i][j] = 1 
        dfs(i,j,0,mp[i][j])
        vis[i][j] = 0
        
print(ans)

 

 

max_val을 구해서 시간초과를 막는다는 것이 신박하다.

 

 

 

 

 

왼쪽 그림은 idx == 1인 경우이다. 

2번째까지 와서 세번째 값을 합한 후 다시 2번째자리로 돌아간다.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

배운 점 : 

 

1. 이차원 배열에서 최댓값을 구하는 방법 

max(max(map))는 불가능 -!

 

max(map(max,map))을 통해 모든 원소에 대해서 비교가 가능하다 -! 

 

 

 

 

참고 블로그 : 

 

https://velog.io/@jajubal/%ED%8C%8C%EC%9D%B4%EC%8D%AC%EB%B0%B1%EC%A4%80-14500-%ED%85%8C%ED%8A%B8%EB%A1%9C%EB%AF%B8%EB%85%B8

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

https://cijbest.tistory.com/87

[백준 14500 : PYTHON] 테트로미노

 

 

복습 :

✅ 20220701

✅ 20220913

🐾 20220916