백준 18290 NM과 K (1) 파이썬

https://www.acmicpc.net/problem/18290

18290번: NM과 K (1)

백트레킹 문제였다.

 

주의할점이 있다면 이전에 방문처리했던 vist배열을 이후에 방문처리하고 다시 원상복구할때 이전 방문처리했던 배열까지 바꿔버리는 부분을 조심해주면 된다.

 

또한 배열 숫자의 크기가 음수도 있으므로 최댓값을 0으로 설정해주면 안 된다.

 

import sys
input = sys.stdin.readline
def back(t,x,y,c):
    global sums,vist
    if t == k:#k개 선택했으므로 최댓값 갱신
        sums = max(sums,c)
        return

        
    for i in range(x,m):
        for j in range(n):
            if not vist[i][j]:
                ch = [(i,j),(i-1,j),(i+1,j),(i,j-1),(i,j+1)]#이번 트레킹에서 나올 수 있는 idx들
                d=[]#이번 트레킹에서 바뀐부분을 저장해줄 배열
                for q,w in ch:
                    if 0<=q<m and 0<=w<n and not vist[q][w]:#idx가 배열 범위 안에 있을때 and 안 바뀐배열만
                        d.append((q,w))#이번 트레킹에서 바뀐 부분이다.
                        vist[q][w]=True
                back(t+1,i,j,c+s[i][j])
                for q,w in d:#이번 트레킹에서 바뀐 배열을 원상복구 해주는 작업
                    vist[q][w]=False
        
m,n,k = map(int,input().split())
vist = [[False]*n for _ in range(m)]
s = [list(map(int,input().split())) for _ in range(m)]
sums= -sys.maxsize#음수가 나올 수 있으니 최솟값으로 설정해준다.
back(0,0,0,0)
print(sums)