백준 18290 : NM과 K (1) (Python)

본문 링크

dx=[-1,1,0,0]
dy=[0,0,-1,1]

def BackTracking(count , total ):

    global Answer

    
    if count==K:
        Answer=max(Answer,total)
        return


    for i in range(N):
        for j in range(M):

            if not visit[i][j]:
                visit[i][j]+=1
                for k in range(4):
                    nx=i+dx[k] ; ny=j+dy[k]
                    if 0<=nx<N and 0<=ny<M:
                        visit[nx][ny]+=1

                BackTracking(count+1 , total+graph[i][j] )

                visit[i][j]-=1
                for k in range(4):
                    nx=i+dx[k] ; ny=j+dy[k]
                    if 0<=nx<N and 0<=ny<M:
                        visit[nx][ny]-=1



N,M,K=map(int,input().split())

graph=[ list(map(int,input().split())) for _ in range(N) ]
visit=[ [0]*M for _ in range(N) ]

Answer=-int(1e9)
BackTracking(0,0 )

print(Answer)

📌 어떻게 접근할 것인가?

백트래킹을 사용해서 풀었습니다.

visit=[ [False]*M for _ in range(N) ]

처음에 방문처리 체크 배열을 이렇게 만들었는데 , 이렇게 할시 제대로 탐식이 안됩니다.

• False False
  False False

• True True
  True False

• True True
  True True

• True False # 여기서 탐색을 해버림.
  False False

위와같은 배열이있을때 이렇게 탐색을 해버리기 때문입니다.

따라서 배열의 초기값을 0 으로 지정했습니다.

재귀로 탐색하면서 탐색가능한 지점이 있으면 그때의 값을 더해주고 깊이가 $K$ 일때 최대값을 매번 갱신해주었습니다.