문제
N×M 크기 격자에서 서로 인접하지 않는 K개의 칸을 선택했을 때, 선택한 칸의 합의 최댓값을 구하라.
입력
첫째 줄에 N, M, K가 주어진다 (1 이상 10 이하, K는 min(4, N*M) 이하). 둘째 줄부터 N×M 격자의 값이 주어진다.
출력
선택한 K개 칸의 합의 최댓값을 출력한다.
예제
| 입력 | 출력 |
|---|---|
1 3 2 1 2 3 | 4 |
풀이
백트래킹으로 K개의 칸을 선택하며, 인접 조건을 확인하여 가지치기한다.
- 격자를 1차원 인덱스로 변환하여 순서대로 탐색한다 (중복 선택 방지)
- 각 칸에 대해
visited배열로 선택 여부를 관리한다 - 현재 칸의 상하좌우에 이미 선택된 칸이 있으면 건너뛴다
- 조건을 만족하면 칸을 선택하고 다음 단계로 재귀한다
- K개 선택 완료 시 합의 최댓값을 갱신한다
핵심 아이디어: K가 최대 4이고 격자가 최대 10×10이므로, 백트래킹으로 충분히 탐색 가능하다. 인접 여부를 4방향으로 확인하여 불가능한 경우를 빠르게 가지치기한다.
코드
package day349;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Day322BOJ18290NMK {
static int N, M, K, ans;
static int[][] map;
static boolean[][] visited;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
K = Integer.parseInt(st.nextToken());
ans = Integer.MIN_VALUE;
map = new int[N][M];
visited = new boolean[N][M];
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < M; j++) {
map[i][j] = Integer.parseInt(st.nextToken());
}
}
recur(0, 0, 0, 0);
System.out.println(ans);
br.close();
}
static int[] dr = { -1, 1, 0, 0 }, dc = { 0, 0, -1, 1 };
private static void recur(int k, int idx, int jdx, int sum) {
if (k == K) {
ans = ans > sum ? ans : sum;
return;
}
boolean check = false;
for (int i = idx; i < N; i++) {
int tmp = idx == i ? jdx : 0;
for (int j = tmp; j < M; j++) {
if (visited[i][j])
continue;
check = true;
for (int dir = 0; dir < 4; dir++) {
int nr = i + dr[dir];
int nc = j + dc[dir];
if (!index(nr, nc) && visited[nr][nc]) {
check = false;
break;
}
}
if (check) {
visited[i][j] = true;
recur(k + 1, i, j, sum + map[i][j]);
visited[i][j] = false;
}
}
}
}
static boolean index(int r, int c) {
return r < 0 || r >= N || c < 0 || c >= M;
}
}복잡도
- 시간: O(C(N*M, K) * K) - 조합 탐색 × 인접 검사
- 공간: O(N * M) - 격자 및 방문 배열