Python/DFS BOJ-14500 테트로미노

Posted on | In

[Python/DFS] BOJ-14500 테트로미노

테트로미노가 놓인 칸에 쓰여 있는 수 들의 합 중 최대값을 구하는 문제다.

어떻게 테트로미노를 지정할 수 있을까?

  1. 가능한 모양을 리스트로 나열
    • 비효율적인 방법이다. 정사각형 수가 늘어난다면 가능한 모양을 세기 어렵다.
    • 시간 초과됨..😲
  2. DFS를 이용해 모양틀 구현 ✔

1. 가능한 모양을 리스트로 나열

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
shapeslist = [[(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), (1, 0), (1, 1), (2, 1)], #Z
        [(0, 0), (1, 0), (1, -1), (2, -1)], #Z
        [(0, 0), (0, 1), (1, 1), (1, 2)], #Z
        [(0, 0), (0, 1), (-1, 1), (-1, 2)], #Z
        [(0, 0), (0, 1), (0, 2), (1, 2)], #L
        [(0, 0), (1, 0), (2, 0), (2, -1)], #L
        [(0, 0), (1, 0), (1, 1), (1, 2)], #L
        [(0, 0), (0, -1), (1, -1), (2, -1)], #L
        [(0, 0), (-1, 0), (-1, 1), (-1, 2)],  #L
        [(0, 0), (1, 0), (2, 0), (2, 1)], #L
        [(0, 0), (0, 1), (0, 2), (-1, 2)], #L
        [(0, 0), (0, 1), (1, 1), (2, 1)], #L
        [(0, 0), (0, 1), (-1, 1), (0, 2)], #ㅓ
        [(0, 0), (1, 0), (1, 1), (2, 0)], #ㅗ
        [(0, 0), (0, 1), (1, 1), (0, 2)], #ㅏ
        [(0, 0), (1, 0), (1, -1), (2, 0)]]#ㅜ

N,M = map(int,input().split()) # N 행 / M 열
graph = [list(map(int,input().split())) for _ in range(N)]

answer=0
for i in range(N) :
    for j in range(M) :
        for shape in shapeslist:
            temp=0
            for s in shape :
                if 0<= i + s[0]< N and 0<= j + s[1]< M :
                    temp += graph[i + s[0]][j + s[1]]
            answer = max(answer, temp)

print(answer)

2. DFS를 이용해 모양틀 구현

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

def dfs(k, temp, r,c):
    global N, M
    global graph
    global answer
    global visited
    global max_val
    steps = [(1,0),(0,1),(-1,0),(0,-1)]
    
    if k==4 :
        answer = max(answer, temp)
        return
    # 탐색횟수를 줄이기 위해 현재 값에 max_value로 값을 다 채워도 answer보다 작을 경우 탐색 중지 
    if temp + (4-k) * max_val < answer:
        return
    for step in steps :
        nr = r + step[0]
        nc = c + step[1]
        if 0<= nr < N and 0<= nc < M :
            if visited[nr][nc]==0 :
                visited[nr][nc] = 1
                if k==2 :
                    # for ㅏ shape
                    dfs(k+1, temp + graph[nr][nc], r, c)
                dfs(k+1, temp + graph[nr][nc], nr, nc)
                visited[nr][nc] = 0
    return 

N, M = map(int, input().split())
graph = [list(map(int,input().split())) for _ in range(N)]
answer=0
visited = [[ 0 for _ in range(M)] for _ in range(N)]
max_val = max(map(max, graph))

for i in range(N) :
    for j in range(M):
        visited[i][j] = 1 
        dfs(1, graph[i][j],i,j)
        visited[i][j] = 0

print(answer)

Reference

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

풀이참고 : https://oranz.tistory.com/7