[Baekjoon] 18290_NM과 K (1)

Silver I

문제(출처: https://www.acmicpc.net/problem/18290)

---

< NM과 K(1) >

 

문제 풀이 

 

구할 수 있는 모든 경우를 다 구하며 최댓값을 구한다.

 

 my solution (Java)

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

public class _18290_ { // NM과 K (1)
	static int arr[][], result;
	static boolean visited[][];
	static int dx[] = { -1, 1, 0, 0 };
	static int dy[] = { 0, 0, -1, 1 };

	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(bf.readLine());

		int n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());
		int k = Integer.parseInt(st.nextToken());

		arr = new int[n][m];
		visited = new boolean[n][m];
		result = Integer.MIN_VALUE;

		for (int i = 0; i < n; i++) {
			st = new StringTokenizer(bf.readLine());
			for (int j = 0; j < m; j++) {
				arr[i][j] = Integer.parseInt(st.nextToken());
			}
		}

		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				visited[i][j] = true;
				search(k - 1, arr[i][j]);
				visited[i][j] = false;
			}
		}

		System.out.println(result);
	}

	private static void search(int k, int sum) {
		if (k == 0) {
			result = Math.max(result, sum);
			return;
		}

		for (int i = 0; i < arr.length; i++) {
			for (int j = 0; j < arr[0].length; j++) {
				if (visited[i][j]) {
					continue;
				}
				boolean flag=false;
				for (int l = 0; l < 4; l++) {
					int a = i + dx[l];
					int b = j + dy[l];
					if (a >= 0 && a < arr.length && b >= 0 && b < arr[0].length) {
						if (visited[a][b]) {
							flag=true;
							break;
						} 
					}
				}
				if (!flag) {
					visited[i][j] = true;
					search(k - 1, sum + arr[i][j]);
					visited[i][j] = false;
				}
			}
		}
	}
}

변수)
n, m, k : 격자판 크기, 선택할 개수
arr : 격자판 정보
visited : 선택 여부
result : 최댓값

 

n, m , k값을 입력받는다. 격자판 정보를 입력받아 arr에 저장한다. 격자판을 전체 탐색하면서 하나를 선택한 후 search 함수를 호출한다. 함수 호출이 종료되면 다음 선택을 위해 선택 표시를 해제한다.

 

최종 최댓값인 result를 출력한다.

 

search(남은 선택 수, 합)

선택을 다 했다면 최댓값을 업데이트한 후 종료한다.

 

격자판을 전체 탐색하면서 이미 선택된 곳이라면 다음 탐색을 한다. 선택된 곳이 아니라면 상하좌우를 살펴보며 선택된 곳이 있는지 판단한다. 선택된 곳이 있다면 그 칸은 선택할 수 없으므로 다음 탐색을 한다. 선택된 곳이 없다면 그 칸을 선택한 후 search 함수를 호출한다. 호출이 끝나면 다음 탐색을 위해 선택을 해제한다.

---

---