[백준] 꽃길

 

package Solution;

import java.util.Scanner;

/*
 * dfs 꽃길만걷즈아아아아
 * 생각보다 쉬웠던 문제
 * */

public class 꽃길 {
	static int N, ans;
	static int arr[][];
	static boolean check[][];
	static int dr[] = {-1,0,1,0};
	static int dc[] = {0,1,0,-1};
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();//평수
		arr = new int[N][N];
		check = new boolean[N][N];
		for(int i =0; i<N; i++) {
			for(int j=0; j<N; j++) {
				arr[i][j] = sc.nextInt();
			}
		}
		dfs(0,0);
		System.out.println(ans);
	}
	private static void dfs(int level, int sum) {
		if(level == 3) {
			ans = Math.min(ans, sum);
			return;
		}
		
		for(int i =0; i<N; i++) {
			for(int j=0; j<N; j++) {
				if(pos(i,j)) {
					int tmp = get(i,j);
					setting(i,j,true);
					dfs(level+1,sum+tmp);
					setting(i,j,false);
				}
			}
		}
		
		
	}
	private static void setting(int r, int c, boolean flag) {
		if(flag) {
			check[r][c] = true;
			for(int i=0; i<4; i++) {
				int nr =r+dr[i];
				int nc =c+dc[i];
				check[nr][nc] = true;
			}
		}else {
			check[r][c]=false;
			for(int i=0; i<4; i++) {
				int nr =r+dr[i];
				int nc =c+dc[i];
				check[nr][nc] = false;
			}
		}
	}
	private static int get(int r, int c) {
		int sum = arr[r][c];
		for(int i =0; i<4; i++) {
			int nr = r + dr[i];
			int nc = c + dc[i];
			sum+=arr[nr][nc];
		}
		
		return sum;
	}
	private static boolean pos(int r, int c) {
		if(check[r][c]) {
			return false;
		}
		for(int i=0; i<4; i++) {
			int nr = r+dr[i];
			int nc = c+dc[i];
			if(!isRange(nr,nc)) {
				return false;
			}
		}
		return true;
	}
	private static boolean isRange(int nr, int nc) {
		if(nr>=1 && nc>=1 && nr<N && nc<N) {
			return true;
		}
		return false;
	}

}