백준 14620번: 꽃길

문제 설명

• https://www.acmicpc.net/problem/14620
• NxN 격자에서 겹치거나 삐져나가지 않게 +모양을 3개를 그릴 수 있는 경우의 수 중, 격자에 적힌 숫자의 합이 최소가 되도록 하는 경우를 찾는 문제입니다.

접근법

• 백트래킹을 활용한 완전탐색을 진행합니다.

정답

import java.util.*;
import java.io.*;

public class Main {
	static int N;
	static int minVal = Integer.MAX_VALUE;

	public static void main(String[] args) throws IOException {
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();
		int[][] board = new int[N][N];

		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				board[i][j] = sc.nextInt();
			}
		}
		boolean[][] v = new boolean[N][N];

		BackT(0, 0, v, board);
		System.out.println(minVal);
	}

	public static void BackT(int depth, int price, boolean[][] v, int[][] board) {
		if (depth == 3) {
			minVal = Math.min(minVal, price);
			return;
		}

		for (int i = 1; i < N - 1; i++) {
			for (int j = 1; j < N - 1; j++) {
				if (Validate(i, j, v)) {
					v[i][j] = true;
					v[i - 1][j] = true;
					v[i + 1][j] = true;
					v[i][j - 1] = true;
					v[i][j + 1] = true;
					int p = board[i][j] + board[i - 1][j] + board[i + 1][j] + board[i][j - 1] + board[i][j + 1];
					BackT(depth + 1, price + p, v, board);
					v[i][j] = false;
					v[i - 1][j] = false;
					v[i + 1][j] = false;
					v[i][j - 1] = false;
					v[i][j + 1] = false;

				}
			}
		}
	}

	public static boolean Validate(int i, int j, boolean[][] v) {
		if (!v[i][j] && !v[i - 1][j] && !v[i + 1][j] && !v[i][j - 1] && !v[i][j + 1])
			return true;
		return false;
	}

}