[BOJ/JAVA] 백준 14620 : 꽃길 (자바)

문제 정보

  문제명   - 꽃길
  난이도   - 실버 II
문제 번호 - 14620번

---

문제 링크

BOJ_S2_14620_꽃길

14620번: 꽃길

---

문제

2017년 4월 5일 식목일을 맞이한 진아는 나무를 심는 대신 하이테크관 앞 화단에 꽃을 심어 등교할 때 마다 꽃길을 걷고 싶었다.
진아가 가진 꽃의 씨앗은 꽃을 심고나면 정확히 1년후에 꽃이 피므로 진아는 다음해 식목일 부터 꽃길을 걸을 수 있다.
하지만 진아에게는 꽃의 씨앗이 세개밖에 없었으므로 세 개의 꽃이 하나도 죽지 않고 1년후에 꽃잎이 만개하길 원한다.
꽃밭은 N*N의 격자 모양이고 진아는 씨앗을 (1,1)~(N,N)의 지점 중 한곳에 심을 수 있다. 꽃의 씨앗은 그림 (a)처럼 심어지며 1년 후 꽃이 피면 그림 (b)모양이 된다.

꽃을 심을 때는 주의할 점이있다. 어떤 씨앗이 꽃이 핀 뒤 다른 꽃잎(혹은 꽃술)과 닿게 될 경우 두 꽃 모두 죽어버린다. 또 화단 밖으로 꽃잎이 나가게 된다면 그 꽃은 죽어버리고 만다.

그림(c)는 세 꽃이 정상적으로 핀 모양이고 그림(d)는 두 꽃이 죽어버린 모양이다.
하이테크 앞 화단의 대여 가격은 격자의 한 점마다 다르기 때문에 진아는 서로 다른 세 씨앗을 모두 꽃이 피게하면서 가장 싼 가격에 화단을 대여하고 싶다.
단 화단을 대여할 때는 꽃잎이 핀 모양을 기준으로 대여를 해야하므로 꽃 하나당 5평의 땅을 대여해야만 한다.
돈이 많지 않은 진아를 위하여 진아가 꽃을 심기 위해 필요한 최소비용을 구해주자!

---

입력

입력의 첫째 줄에 화단의 한 변의 길이 N(6≤N≤10)이 들어온다.
이후 N개의 줄에 N개씩 화단의 지점당 가격(0≤G≤200)이 주어진다.

---

출력

꽃을 심기 위한 최소 비용을 출력한다.

---

예제 입력/출력

예제 입력	예제 출력
6 1 0 2 3 3 4 1 1 1 1 1 1 0 0 1 1 1 1 3 9 9 0 1 99 9 11 3 1 0 3 12 3 0 0 0 1	12

---

알고리즘 분류

● 브루트포스 알고리즘

---

소스코드

package Lv2_Silver;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
/**
 * @author HanHoon
 * @category 브루트포스 알고리즘
 * https://www.acmicpc.net/problem/14620
 */
public class BOJ_S2_14620_꽃길 {
	static int result = Integer.MAX_VALUE;
	// 상하좌우
	static int[] dRow = {-1, 1, 0, 0};
	static int[] dCol = { 0, 0,-1, 1};
	public static void backtracking(int N, int[][] map, boolean[][] isSelected, int sum, int count) {
		// 꽃을 3개 심으면 return;
		if(count == 3) {
			result = Math.min(result, sum);
			return;
		}
		// 가장자리는 꽃을 심지 않는다.
		for (int i = 1; i < N-1; i++) {
			for (int j = 1; j < N-1; j++) {
				// 상하좌우 꽃심기가 가능하다면
				if(possible(i, j, isSelected)) {
					// 꽃을 심고 비용을 더해준다.
					isSelected[i][j] = true;
					sum += map[i][j];
					// 상하좌우 비용
					for (int index = 0; index < 4; index++) {
						int next_Row = i + dRow[index];
						int next_Col = j + dCol[index];
						isSelected[next_Row][next_Col] = true;
						sum += map[next_Row][next_Col];
					}
					backtracking(N, map, isSelected, sum, count+1);
					isSelected[i][j] = false;
					sum -= map[i][j];
					// 상하좌우 비용
					for (int index = 0; index < 4; index++) {
						int next_Row = i + dRow[index];
						int next_Col = j + dCol[index];
						isSelected[next_Row][next_Col] = false;
						sum -= map[next_Row][next_Col];
					}
				}
			}
		}
	}
	public static boolean possible(int row, int col, boolean[][] isSelected) {
		// 상하좌우 범위에 이미 꽃이 심어져있다면 false
		for (int index = 0; index < 4; index++) {
			int next_Row = row + dRow[index];
			int next_Col = col + dCol[index];
			// 범위밖은 애초에 가지 않으므로 사용중인지만 판단한다.
			if(isSelected[next_Row][next_Col] == true)
				return false;
		}
		return true;
	}
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = null;
		// 화단의 한 변의 길이
		int N = Integer.parseInt(br.readLine());
		int[][] map = new int[N][N];
		boolean[][] isSelected = new boolean[N][N];
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			for (int j = 0; j < N; j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		backtracking(N, map, isSelected, 0, 0);
		System.out.println(result);
		br.close();
	}
}

 

---

BaekJoon List

BaekJoon List

---

  

기회는 준비된 자에게 찾아온다.

 

---