<백준 18290번-python> NM과 K (1)
06 Mar 2021시간 제한 : 2초
메모리 제한 : 512 MB
정답 비율 : 22.686%
출처 : 백준-18290번 https://www.acmicpc.net/problem/18290
문제
크기가 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개의 칸을 선택할 수 있는 경우만 입력으로 주어진다.
내가 적어본 문제 풀이
격자판에 들어가는 숫자가 특정한 규칙없이 들어가 있으므로 완전 탐색을 해야 한다. 입력 값 N, M이 1 ≤ N, M ≤ 10 이기 때문에 최대 100칸의 격자판이 만들어 질 수 있고, 선택은 최대 4개의 칸을 선택할 수 있으므로, 최악의 경우 조합 계산으로 10_C_4 = 1009998*97 = 94,109,400 = 10^9이다. 따라서 사실상 모든 조합을 탐색하는 방법은 무리가 있지만 그냥 한 번 시도해 봤다.
from itertools import combinations, product
N, M, K = map(int, input().rstrip().split())
grid = []
near_idx = [[-1, 0], [0, 1], [1, 0], [0, -1]]
res = []
for _ in range(N):
grid.append(list(map(int, input().rstrip().split())))
all_combi = combinations(product([x for x in range(N)], [y for y in range(M)]), K)
입력을 다음과 같이 받고, combinations와 product를 이용해 격자판의 인덱스 (x, y)인 총 N*M개 중 K개를 선택하는 모든 조합을 구한다.
예를 들어 N = 5, M = 5, K = 3이면, all_combi는 아래와 같다.
# 생략 ...
((1, 4), (2, 4), (3, 3))
((1, 4), (2, 4), (3, 4))
((1, 4), (2, 4), (4, 0))
((1, 4), (2, 4), (4, 1))
((1, 4), (2, 4), (4, 2))
((1, 4), (2, 4), (4, 3))
((1, 4), (2, 4), (4, 4))
((1, 4), (3, 0), (3, 1))
((1, 4), (3, 0), (3, 2))
((1, 4), (3, 0), (3, 3))
((1, 4), (3, 0), (3, 4))
((1, 4), (3, 0), (4, 0))
((1, 4), (3, 0), (4, 1))
((1, 4), (3, 0), (4, 2))
((1, 4), (3, 0), (4, 3))
((1, 4), (3, 0), (4, 4))
((1, 4), (3, 1), (3, 2))
((1, 4), (3, 1), (3, 3))
((1, 4), (3, 1), (3, 4))
((1, 4), (3, 1), (4, 0))
((1, 4), (3, 1), (4, 1))
((1, 4), (3, 1), (4, 2))
((1, 4), (3, 1), (4, 3))
# 생략 ...
위 조합들을 모두 탐색하면서 칸의 합이 최대가 되는 조합을 찾으면 되는데, 조건이 선택한 두 칸이 인접하면 안되므로 이를 고려하면서 탐색한다.
for combi in all_combi:
combi_sum = 0
near = False
for i, j in combi:
for near_i, near_j in near_idx:
if (i+near_i, j+near_j) in combi: # 인접한 칸인지 검사
near = True
break
if near: # 인접한 칸일 경우
break
else:
combi_sum += grid[i][j]
if not near:
res.append(combi_sum)
print(max(res))
효울이 좋지 않은 코드로 당연히 시간 초과가 난다.
하지만 신기하게도 pypy3으로는 간신히 통과된다.
어쨌든 실력 향상을 위해 위 코드를 효율 좋은 방법으로 탐색해 보기 위해 DFS로 다시 짜봤다. 몇 번을 시도하면서 계속해서 방법을 개선해 나갔는데 마지막에 개선된 방법은,
- 격자판의 모든 위치에서 1번 씩 dfs 호출
- 격자판에서 현재 선택한 칸의 인접한 구역 설정
- 다음 칸부터 다시 탐색 시작
- 인접한 구역이 아니면 dfs 호출
level = K면, 최대값 비교 및 저장- 한 재귀가 모든 구역을 다 탐색하면 인접한 구역 해제
코드와 같이 설명해 보자면, 우선 1번을 위해 아래와 같이 변수들을 초기화 한다.
def dfs(now_i, now_j, level, now_sum):
# ...
if __name__ == "__main__":
N, M, K = map(int, input().rstrip().split())
grid = []
for _ in range(N):
grid.append(list(map(int, input().rstrip().split())))
near_idx = [[0, 1], [1, 0]]
near_check = [[0]*M for _ in range(N)]
res = -40001
for start_i in range(N):
for start_j in range(M):
dfs(start_i, start_j, 1, grid[start_i][start_j])
print(res)
여기서 원래 인접한 구역은 헌재 칸을 기준으로 상,하,좌,우 4군데지만, 알고리즘 상 이미 탐색한 구역은 순회하지 않도록 만들어 왼쪽과 위는 어차피 나중에 호출되는 재귀에서 탐색할 일이 없어 오른쪽과 아래만 검사하기 위해 near_idx를 [[0, 1], [1, 0]]으로 초기화 했다.
near_check는 현재 선택한 칸들의 인접한 구역을 저장하기 위한 2차원 리스트다.
res의 초기화 값은 혹시 모든 칸이 최소 값인 -10000일 경우를 대비하기 위해 -40001로 초기화 했다.
def dfs(now_i, now_j, level, now_sum):
if level == K:
global res
res = max(res, now_sum)
return
for near_i, near_j in near_idx:
temp_i, temp_j = now_i+near_i, now_j+near_j
if temp_i<N and temp_j<M:
near_check[temp_i][temp_j] += -1
# ...
for near_i, near_j in near_idx:
temp_i, temp_j = now_i+near_i, now_j+near_j
if temp_i<N and temp_j<M:
near_check[temp_i][temp_j] += 1
재귀 탈출 조건은 if level == K으로 level이 선택한 칸의 개수를 의미한다. 또한 많이 틀리면서 배운 것중에 global변수 활용인데, 파이썬에서 전역 변수를 사용하기 위해서는 사용하려는 지역(예를 들어 함수 안)에서 global 키워드를 사용해 현재 스코프 밖에 있는 변수를 사용하겠다고 알려야 한다. 특히 재귀에서는 전역 변수 활용이 매우 효울적이기 때문에 알면 편하다.
그 다음 for문은 인접한 구역을 저장하기 위함인데, 어차피 오른쪽과 아래만 검사하므로 인덱스 검사도 N과 M 이상인지만 검사해 주면 된다. 단, 해당 지역을 단순히 -1같은 수로 초기화 하지 않고 더해준 이유는 인접한 구역이 곂칠 경우 때문이다. 이럴 경우 나중에 인접한 구역을 해제할 때 문제가 발생한다.
# (0,1)과 (1,0) 선택 -> 선택한 지역은 편의상 1로 표시
# 그냥 -1로 초기화 한 경우
|0|1|-1|
|1|-1|0|
|-1|0|0|
# -1을 더한 경우
|0|1|-1|
|1|-2|0|
|-1|0|0|
위와 같은 상황에서 (1,0)의 재귀가 끝나 인접한 구역을 해제해야 할 때, -1인 지역을 그냥 단순히 0으로 초기화 하는 등의 방법을 사용하면 (0,1)에서 아래에 인접한 구역이 사라져 버린다. 다른 방식으로 해제할 수 있겠지만 -1을 더하면 해제할 때 다시 1을 더해주면 된다.
# 그냥 -1로 초기화 한 경우 -> 0으로 초기화
|0|1|-1|
|1|0|0|
|0|0|0|
# -1을 더한 경우 -> 1 더하기
|0|1|-1|
|1|-1|0|
|0|0|0|
이제 중간 부분인 다음 칸을 탐색하는 로직이다.
for j in range(now_j+1, M):
if near_check[now_i][j] == 0:
dfs(now_i, j, level+1, now_sum+grid[now_i][j])
for i in range(now_i+1, N):
for j in range(M):
if near_check[i][j] == 0:
dfs(i, j, level+1, now_sum+grid[i][j])
처음에는 그냥 (0,0)부터 시작하도록 했다. 하지만, 이는 탐색한 조합을 또 다시 탐색하므로 효율도 나쁘고 dfs라고 할 수도 없다. 때문에 따로 탐색한 구역을 저장하는 변수와 로직이 필요한데, 그래도 되지만, 현재 위치의 다음 칸부터 탐색해도 된다. 따라서 2개의 반복 구조를 만들었다. 처음 구조는 현재 칸에서 같은 row에 위치한 나머지 칸들을 순회하고, 그 다음은 현재 row+1의 첫 번째 칸(column=0)부터 순회한다.
이 구조가 번잡하면 각 칸에 고유의 번호를 붙인 다음 그 번호들을 담는 리스트를 만들어야 한다. 즉, 2차원 리스트를 1차원 리스트로 변환해 순회하면 2중 for문도 필요없이 약간의 인덱스 계산으로 코드 자체는 더 간결하게 만들 수 있다.
전체 코드 : https://github.com/on1ystar/algorithm-problem-solving-codes/blob/master/BOJ/18290.py
사실 해보면서 재귀에 대한 이해에서 부족한 부분을 너무 많이 느낌과 동시에 또 많이 배웠다.