[백준/브루트포스] 18290 NM과 K (1) (Python, 파이썬)

 

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

18290번: NM과 K (1)

 

앞서 풀었던 N과 M 문제의 심화 버전이다.

N과 M문제는 1차원 배열이었다면, 이 문제는 2차원 배열이다.

 

그러나 풀고자 하는 원리는 같으므로 재귀를 통해 해결할 수 있다.

그러나 문제는 시간복잡도이다..🥲

 

시간을 줄이는 가장 좋은 방법은 중복해서 계산하는 값을 찾아내서 없애는 것이다.

이 문제에서는 go함수에서의 for문에서 중복 계산이 일어날 수 있다.

이를 해결하기 위해 (px, py)를 추가했다.

(1, 2), (1, 5), (3, 4)를 선택한 후에 (1, 5), (1, 2), (3, 4)를 또다시 선택하는 경우를 피하는 것이다.

 

같은 행에서도 중복된 선택을 피하기 위해서 이전에 선택한 행과 같은 행인 경우와 아닌 경우로 나눌 수 있다. 

 

import sys
input = sys.stdin.readline

n, m, k = map(int, input().split())
arr = [list(map(int, input().split())) for _ in range(n)]
visited = [[False] * m for _ in range(n)]

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

answer = -1000000

def go(px, py, index, sum):
    if index == k:
        global answer
    
        if answer < sum:
            answer = sum
        
        return

    for x in range(px, n):
        for y in range(py if x==px else 0, m):
            # 현재 위치 방문했었는지 확인
            if visited[x][y]:
                continue

            ok = True
            # 동서남북 방문 했었는지 확인
            for i in range(4):
                nx = x + dx[i]
                ny = y + dy[i]

                if 0 <= nx < n and 0 <= ny < m:
                    if visited[nx][ny]:
                        ok = False            
            # 방문
            if ok:
                visited[x][y] = True
                go(x, y, index+1, sum+arr[x][y])
                visited[x][y] = False


go(0, 0, 0, 0)

print(answer)