[BOJ] 14500

문제

백트래킹, dfs

me

오랜만에 풀었네 훌찌락,,

import sys
input=sys.stdin.readline

N,M=map(int,input().split())
box=[list(map(int,input().split())) for _ in range(N)]
#visited=[[False]*M for _ in range(N)]
def dfs(mino,sum):
    global max_num
    dx=[-1,0,+1,0]
    dy=[0,-1,0,+1]
    if len(mino)==4:
        for m in mino: print(m,box[m[0]][m[1]])
        max_num=max(max_num,sum)
        print(max_num)
    else:
        x,y=mino[-1]
        for i in range(4):
            nx=x+dx[i]; ny=y+dy[i];
            if  [nx,ny] not in mino and (-1<nx<N and -1<ny<M):
                mino.append([nx,ny])
                dfs(mino,sum+box[nx][ny])
                mino.pop()
        if len(mino)==3:
            x,y=mino[1] # 중앙
            for i in range(4):
                nx=x+dx[i]; ny=y+dy[i];
                if [nx,ny] not in mino and (-1<nx<N and -1<ny<M):
                    mino.append([nx,ny])
                    dfs(mino,sum+box[nx][ny])
                    mino.pop()

max_num=0
for i in range(N):
    for j in range(M):
        #visited[i][j]=True
        dfs([[i,j]],box[i][j])
print(max_num)

• 근데 6608ms 나옴
• ^^..
• 푼게 푼 것이 아니네

others

출처

import sys; input = sys.stdin.readline

def dfs(r, c, idx, total):
    global ans
    if ans >= total + max_val * (3 - idx):
        return
    if idx == 3:
        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 idx == 1:
                    visit[nr][nc] = 1
                    dfs(r, c, idx + 1, total + arr[nr][nc])
                    visit[nr][nc] = 0
                visit[nr][nc] = 1
                dfs(nr, nc, idx + 1, total + arr[nr][nc])
                visit[nr][nc] = 0


N, M = map(int, input().split())
arr = [list(map(int, input().split())) for _ in range(N)]
visit = [([0] * M) for _ in range(N)]
dr = [-1, 0, 1, 0]
dc = [0, 1, 0, -1]
ans = 0
max_val = max(map(max, arr))

for r in range(N):
    for c in range(M):
        visit[r][c] = 1
        dfs(r, c, 0, arr[r][c])
        visit[r][c] = 0

print(ans)

• 현재 만들 수 있는 가장 큰 값을 가지고 가지치기 하는 것
  가장 큰 값을 가지고 현재 max와 total+큰 값*(3-idx)를 비교해서 아무리 큰 값이 남은 칸만큼 더해져도 max보다 작으면 더이상 탐색하지 않는 걸로 가지치기!
• ㅗ 모양 만들기 위해서 블럭 2개가 선택됐을 때, 방금 추가된 거 말고 이전의 것에서 4방향 탐색하면 👍