[백준] 18290. NM과 K (1) (Java)

 

문제

18290번: NM과 K (1)

 

알고리즘

브루트포스, 백트래킹

 

풀이

원소가 최대 100개, K가 최대 4이고 100C4 = 3,921,225 이므로 브루트포스로 문제를 해결한다.

 

각 칸이 더할 수 있는 칸인지 저장하기 위해 board와 동일한 크기의 boolean형 배열을 만들고,

dfs(int count, int sum, int y, int x) 를 호출한다.

count는 더한 수의 개수, sum은 합, y는 현재 열의 인덱스, x는 현재 행의 인덱스이다.

 

count가 K가 되었다면 (K개의 원소를 더했으면) max 값을 갱신하고 반환한다.

count가 K보다 작다면 (y, x) 부터 더할 수 있는 수를 찾는다.

 

더할 수를 찾으면 그 수와 상하좌우의 수를 더할 수 없으므로 해당 위치의 visited 값을 임시로 tmp 배열을 만들어 저장하고,

visited를 false로 바꾼 후 다음 dfs (count + 1, sum + board[i][j], i, j + 1)를 호출한다.

호출한 dfs가 반환되면 그 수를 뽑지 않은 것으로 돌려놔야하므로 false로 바꾼 5가지 좌표의 값을 저장해놨던 visited 값으로 돌려놓는다.

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	static int[] dy = { -1, 1, 0, 0 };
	static int[] dx = { 0, 0, -1, 1 };
	static int N, M, K, board[][], max;
	static boolean[][] visited;

	public static void main(String[] args) throws IOException {
		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());

		board = new int[N][M];
		visited = new boolean[N][M];
		max = Integer.MIN_VALUE;

		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			for (int j = 0; j < M; j++) {
				board[i][j] = Integer.parseInt(st.nextToken());
			}
		}

		dfs(0, 0, 0, 0);
		System.out.println(max);
	}

	static void dfs(int count, int sum, int y, int x) {
		if (count == K) {
			max = Math.max(max, sum);
			return;
		}

		for (int i = y; i < N; i++) {
			for (int j = i == y ? x : 0; j < M; j++) {
				if (!visited[i][j]) {
					boolean[] tmp = new boolean[dy.length]; 
					visited[i][j] = true;
					for (int k = 0; k < dy.length; k++) {
						int ny = i + dy[k];
						int nx = j + dx[k];
						if (!(ny < 0 || ny >= N || nx < 0 || nx >= M)) {
							tmp[k] = visited[ny][nx];
							visited[ny][nx] = true;
						}
							
					}

					dfs(count + 1, sum + board[i][j], i, j + 1);

					visited[i][j] = false;
					for (int k = 0; k < dy.length; k++) {
						int ny = i + dy[k];
						int nx = j + dx[k];
						if (!(ny < 0 || ny >= N || nx < 0 || nx >= M))
							visited[ny][nx] = tmp[k];
					}
				}
			}
		}
	}
}