# [Silver I] NM과 K (1) - 18290

[Silver I] NM과 K (1) - 18290

문제 링크

성능 요약

메모리: 31120 KB, 시간: 2996 ms

분류

백트래킹, 브루트포스 알고리즘

제출 일자

2024년 11월 5일 14:53:46

문제 설명

크기가 N×M인 격자판의 각 칸에 정수가 하나씩 들어있다. 이 격자판에서 칸 K개를 선택할 것이고, 선택한 칸에 들어있는 수를 모두 더한 값의 최댓값을 구하려고 한다. 단, 선택한 두 칸이 인접하면 안된다. r행 c열에 있는 칸을 (r, c)라고 했을 때, (r-1, c), (r+1, c), (r, c-1), (r, c+1)에 있는 칸이 인접한 칸이다.

입력

첫째 줄에 N, M, K가 주어진다. 둘째 줄부터 N개의 줄에 격자판에 들어있는 수가 주어진다.

출력

선택한 칸에 들어있는 수를 모두 더한 값의 최댓값을 출력한다.

 

 

풀이

import sys
 
N , M , K = map(int , sys.stdin.readline().split())
ans = -10000000000
mat = [[i for i in map(int , sys.stdin.readline().split())] for w in range(N)]
global visited
visited = [ [False]*M for _ in range(N)] # (r-1, c), (r+1, c), (r, c-1), (r, c+1)
 
 
 
# def check_visitied():
#     for i in range(len(visited)):
#             print(visited[i])
        
#     print("----------------------")
 
 
def check(px, py, index, sum):
    # print(sum)
    if index == K :
        global ans
        # check_visitied()
        ans = max(sum , ans)
        return 
    
    dx = [1,-1,0,0]
    dy = [0,0,1,-1]
 
    # py if x == px else 0, 이게 왜 필요하지?
    # px == x라는 것은 내가 재귀함수를 실행하는 행이 이전에 실행했던 재귀함수의 행과 중복되는지 확인한다.
    # 따라서 지금 재귀를 돌리는 행이 이전 재귀의 행과 같은 부분은 0부터가 아닌 py부터 진행해도 무방하다.
    # (이전 재귀에서 탐색했기 때문)
    for x in range(px, N):
        for y in range(py if x == px else 0, M):
            if(visited[x][y]):
                continue
 
            flag = True
            for i in range(4):
                mx = x+dx[i]
                my = y+dy[i]
 
                # 해당되는 범위가 밖에 있는 경우.
                if(0 > mx or N <= mx or 0 > my or M <= my):
                    continue
                
                if(visited[mx][my]):
                    flag = False
                    break
 
            if(flag):
                visited[x][y] = True
                check(x, y, index+1, sum+mat[x][y])
                visited[x][y] = False
 
check(0,0,0,0)    
print(ans)

 

 

재귀함수는 어릴 때 풀었던 전개도 문재 같다는 생각이든다. 삼차원으로 이루어지는 작업을 코드로써 이차원으로 옮긴 것 같아 복잡하게 느껴진다.