[CLASS 3]백준 14500번 - 테트로미노

14500번 : 테트로미노

 

일단 문제를 처음 봤을때 부터 브루트포스로 풀어야 한다고 생각했다. 왜냐하면 종이 위에 적혀 있는 숫자에 어떤 규칙성이 없기 때문에 무조건 종이 위 모든 숫자를 돌아다니면서 확인해야 한다고 생각했기 때문이다. 그래서 처음엔 이런 코드를 작성했다.

 

내 코드:

# dawitblog.tistory.com
from sys import stdin
input = stdin.readline

dr = [0,0,1,-1,1,1]
dc = [1,-1,0,0,1,-1]
move = ['005','205','214','034','021','000','222','220','221','002','300','330','331','003','200','202','212','020','030']

def findMax(mat,tr,tc):
    m = 0
    for step in move:
        newR = tr
        newC = tc
        val = mat[tr][tc]
        count = 1
        for s in step:
            newR += dr[int(s)]
            newC += dc[int(s)]

            if 0<=newR<r and 0<=newC<c:
                count += 1
                val += mat[newR][newC]
            else:
                break
        if count == 4:
            m = max(m,val)
    
    return m

r, c = map(int,input().split())
mat = [list(map(int,input().split())) for _ in range(r)]

realMax = 0
for R in range(r):
    for C in range(c):
        realMax = max(findMax(mat,R,C),realMax)

print(realMax)

 

진정한 의미로서의 브루트포스(..) 가 아닐까 싶은 코드이다. 그냥 노가다로 모든 모양에 대해 이동하고 더하면서 최대값을 찾는다. 직관적이지만 좀 멍청하고 느린 방법이다. 맞긴 했지만 7248ms로 파이썬 제한시간 8초보다 약간 빨라서 간신히 통과했다.

 

그렇다면 어떻게 하면 시간을 줄일 수 있을까? 라고 생각하다가 맞은 분들의 코드를 봤다. 바로 DFS로 풀면 되는 것이다! ㅗ 모양 때문에 안 될 것이라고 생각했는데 중간에 간단한 처리만 해주면 DFS로도 충분히 구현할 수 있었다. 다음은 DFS코드이다.

 

내 코드(DFS):

# dawitblog.tistory.com
from sys import stdin
input = stdin.readline

r,c = map(int,input().split())
mat = [list(map(int,input().split())) for _ in range(r)]

maxValue = max(max(mat))

visited = [[False]*c for _ in range(r)]
drc = [(1, 0), (0, -1), (-1, 0), (0, 1)]
# DFS
def dfs(k,s,tr,tc):
    global realMax

    # 나머지를 모두 최대값만 더했을때도 이미 저장된 값보다 작다면
    if s + maxValue*(3-k) <= realMax:
        return
    if k == 3:
        realMax = max(realMax,s)
        return

    for dr,dc in drc:
        newR = tr + dr
        newC = tc + dc

        if 0<=newR<r and 0<=newC<c and not visited[newR][newC]:
            if k == 1:
                visited[newR][newC] = True
                dfs(k+1,s+mat[newR][newC],tr,tc)
                visited[newR][newC] = False
            
            visited[newR][newC] = True
            dfs(k+1,s+mat[newR][newC],newR,newC)
            visited[newR][newC] = False

realMax = 0
for R in range(r):
    for C in range(c):
        visited[R][C] = True
        dfs(0,mat[R][C],R,C)
        visited[R][C] = False

print(realMax)

 

이렇게 작성해주면 비약적인 시간 감소를 볼 수 있다.(256ms) 그래프 탐색(BFS,DFS)는 내 생각보다 쓸데가 엄청 많은 것 같다.