[Algo Rhythm🕺💃] BOJ 18290 - NM과 K(1)

💫문제 분석

크기가 $n \times m\ (1 \le n,\ m \le 10)$인 격자판을 $g$라고 하자. $g$의 각 칸에는 정수가 하나씩 들어있는데 인접한 칸들을 제외하고 $k\ (1 \le k \le \min (4, n \times m))$개의 칸을 선택하여 각 칸에 들어있는 모든 수들을 더할 때 나올 수 있는 값들 중 최댓값을 구해야 한다.

$g$의 각 칸을 하나의 vertex라고 생각해보자. 그렇다면 이 문제는 $n \times m$개의 vertex들 중에서 인접한 칸들을 제외하고 $k$개의 vertex를 선택할 때 얻을 수 있는 최댓값을 구하는 backtracking 문제로 이해할 수 있다.

 

🔥문제 풀이

$n \times m$개의 칸 중 $k$개의 칸을 선택할 때 한 가지 조건은 이미 선택된 칸들과 인접한 칸은 선택할 수 없다는 것이다. 이를 위해 각 칸의 방문 여부를 나타내는 $n \times m$ 크기의 정수형 배열 $v$를 생성했다.

$v$는 그 값이 0이면 방문하지 않음을, 0보다 크면 방문함을 나타낸다. $bool$형 배열이 아니라 정수형을 사용한 이유는 선택한 칸들 중 인접한 칸이 중복될 수 있기 때문이다. 간단한 예시는 아래와 같다.

 

문제에서 요구하는 최댓값을 구하는 함수를 $f$라고 할 때, $f$는 아래와 같다.

 

✨복잡도 분석

격자판 $g$의 크기를 $n \times m\ (1 \le n,\ m \le 10)$라고 하고 선택해야 하는 칸의 수를 $k\ (1 \le k \le \min (4, n \times m))$라고 할 때 시간 복잡도와 공간 복잡도는 다음과 같다.

⏰시간 복잡도 : $O((nm)^k)$

• $g$를 만드는데 $O(nm)$이 소요됨
• 최댓값을 구하는 함수 $f$는 recursive case마다 $O(nm)$이 소요되는데 depth가 k일 때까지 반복하기 때문에 $O((nm)^k)$가 소요됨

🏠공간 복잡도 : $O(nm)$

• $g$를 저장하는데 $O(nm)$이 소요됨
• $v$를 저장하는데 $O(nm)$이 소요됨

 

🌈코드

 

🌏문제 출처

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

18290번: NM과 K (1)