[백준] 18290번 NM과 K (1) ★★★

💡문제접근

• 백트래킹을 통해 K개를 구해 나올 수 있는 모든 수들을 더한 최댓값을 구하는 문제였는데 처음에는 문제를 잘못 이해해서 선택한 두 칸이 인접하면 안된다는 것을 한 칸을 고르고 대각선으로만 가야한다고 착각해서 많은 시간을 소모했다.
• 하나의 칸을 골랐을 때 그 칸을 기준으로 상하좌우로 이동했다면 동작을 멈추고 그게 아니라면 백트래킹을 수행해 최댓값을 구하는 방법으로 코드를 작성했다.

💡코드

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 6)

N, M, K = map(int, input().split())  
array = [list(map(int, input().split())) for _ in range(N)]
visited = [[False] * M for _ in range(N)]
max_sum = -int(1e9)

def DFS(Y, X, cnt, Sum):
    global max_sum
    # K개를 뽑았을 때 최댓값을 리턴
    if cnt == K:
        max_sum = max(max_sum, Sum)
        return
    dy = [0, 1, 0,- 1]
    dx = [-1, 0, 1, 0]
    for y in range(Y, N):
        for x in range(X if y == Y else 0, M):
            if visited[y][x]:
                continue
			
            # 상하좌우 탐색
            for k in range(4):
                ny = y + dy[k]
                nx = x + dx[k]
                # 네 방향을 모두 돌렸는데 탐색하지 않았다면?
                if 0 <= ny < N and 0 <= nx < M and visited[ny][nx]:
                    break
            else:
                visited[y][x] = True
                DFS(y, x, cnt+1, Sum+array[y][x])
                visited[y][x] = False

DFS(0, 0, 0, 0)
print(max_sum)

💡소요시간 : 3d