졍's 기술 블로그

NM과 K (1)

티어 : Silver 1
시간 제한 : 2 초
메모리 제한 : 512 MB
알고리즘 분류 : 브루트포스 알고리즘, 백트래킹

문제

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

입력

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

출력

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

제한

• 1 ≤ N, M ≤ 10
• 1 ≤ K ≤ min(4, N×M)
• 격자판에 들어있는 수는 -10,000보다 크거나 같고, 10,000보다 작거나 같은 정수이다.
• 항상 K개의 칸을 선택할 수 있는 경우만 입력으로 주어진다.

예제 입출력

Algorithm

back tracking - 재귀 이용
1. graph 구현
2. 2중 for문을 돌면서 인접한 칸이 아니고 visited = False인 칸의 값을 stack에 append
3. append한 칸의 visited 값을 True로 변경하고 재귀함수 호출
4. 재귀함수 return되면 stack에서 pop하고 visited값 False로 변경
5. stack의 길이가 K가 되면 합을 구하고 합의 최댓값으로 갱신

Code

def back_tracking(x, y):
    global answer
    global sum_
    
    # stack의 길이가 K가 되면 합을 구하고 합의 최댓값 갱신
    if len(stack) == K:
        if answer < sum_:
            answer = sum_
    else:
        while x < N:
            while y < M:
                # stack이 비어있으면
                if not stack:
                    # (x, y)의 visited값이 False면 append
                    if not visited[x][y]:
                        stack.append((x, y))
                        visited[x][y] = True
                        sum_ += int(graph[x][y])
                        # 이 때의 x, y값을 인자로 재귀함수 호출
                        back_tracking(x, y)
                        # 재귀함수가 return되면 pop하고 visited False로 변경
                        stack.pop()
                        visited[x][y] = False
                        sum_ -= int(graph[x][y])
                    
                # (x, y)의 visited = False이고 인접한 칸이 아니면 append
                elif not visited[x][y] and (x-1, y) not in stack and (x+1, y) not in stack and (x, y-1) not in stack and (x, y+1) not in stack:
                    stack.append((x, y))
                    visited[x][y] = True
                    sum_ += int(graph[x][y])
                    # 이 때의 x, y값을 인자로 재귀함수 호출
                    back_tracking(x, y)
                    # 재귀함수가 return되면 pop하고 visited False로 변경
                    stack.pop()
                    visited[x][y] = False
                    sum_ -= int(graph[x][y])

                y = y + 1
            x = x + 1
            y = 0

import sys
input = sys.stdin.readline

N, M, K = map(int, input().split())
graph = []
for _ in range(N):
    graph.append(input().rstrip().split())
    
global answer
global sum_
answer = -10000 * K - 1
sum_ = 0
stack = []
visited = [[False for _ in range(M)] for _ in range(N)]
back_tracking(0, 0)
print(answer)

메모리: 30864 KB
시간: 5880 ms