[백준] 14500번 테트로미노

백준_14500

감이 안 잡혀서 다른 분의 코드를 한 번 살펴본 후, 풀었다

ㅜ 모양의 블록을 제외한 나머지 블록은 회전하더라도 4번 안에 모두 탐색 가능하므로 dfs로 4방향을 확인해준다
ㅜ 모양의 경우 4방향 중에서 한 방향을 제외한 값들의 합을 더한다
탐색할 위치가 그래프 값을 벗어나는 경우도 있을 수 있으므로, 탐색 가능한 위치(score)의 갯수가 3이거나 4인 경우에만 탐색한다

n, m = map(int, input().split())
graph = [list(map(int, input().split())) for _ in range(n)]
visited = [[0]*m for _ in range(n)]
answer = 0

dx = [0,0,1,-1]
dy = [1,-1,0,0]
#ㅜ 모양을 제외한 4개의 모양은 4번 안에 모두 탐색 가능
def dfs(x, y, cnt, score):
    global answer
    if cnt==4:
        answer = max(answer, score)
        return

    for k in range(4):
        nx = x+dx[k]
        ny = y+dy[k]
        if 0<=nx<n and 0<=ny<m and not visited[nx][ny]:
            visited[nx][ny] = 1
            dfs(nx,ny,cnt+1, score+graph[nx][ny])
            visited[nx][ny] = 0

#ㅜ 모양의 최대값 탐색
def lastblock(x,y):
    global answer
    score = []
    for k in range(4):
        nx = x+dx[k]
        ny = y+dy[k]
        if 0<=nx<n and 0<=ny<m:
            score.append(graph[nx][ny])

    if len(score)==3:
        tmp = graph[x][y] + sum(score)
        answer = max(answer, tmp)
    elif len(score)==4:
        for i in range(len(score)):
            tmp = graph[x][y] + sum(score[:i]+score[i+1:])
            answer = max(answer, tmp)

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

        lastblock(i,j)

print(answer)

최근에 봤던 코테에서 이 문제랑 굉장히 비슷한 문제가 나와서 풀어보았다. 꽤 자주 봤던 문제였는데 왜 한 번도 안 풀어봐서 못 풀게 됐는지..좀 아쉬웠다