[백준 14620] 꽃길 (자바)

백준 14620번 꽃길 (자바)

 

 

 

출처

www.acmicpc.net/problem/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)이 주어진다.

 

 

 

출력

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

 

 

 

 

입출력 예

 

 

 

걸린 시간

!~!~56분~!~!

 

 

 

접근 방법

기본적인 백트래킹에 응용이 필요한 문제!

최근 완탐연습이 부족한 것 같아 오랜만에 풀어보았다.

 

일단 상하좌우에 꽃잎이 존재해야하기 때문에 길이 1만큼 테두리는 고려할 필요가 없다.

그래서 2,2부터 탐색을 시작했다.(시간 줄이기 위해!)

 

visit배열은 그칸에 꽃잎이 있는지 판단한다. 때문에 방문하지 않았고 && 상하좌우에 꽃잎이 없는 경우에만 탐색한다.

이때, 비용을 구해야 하므로 상하좌우의 비용을 더해준다.

그 후, 백트래킹으로 합을 누적시키면서 찾은 꽃이 3개가 되는 경우 최소 합을 계속 갱신해준다.

재귀가 끝난 후에는 방문처리를 해제해야 하기 때문에 꽃이 있던 위치를 모두 false로 변경한다.

 

 

 

 

내 코드

	package guhyun;
	import java.io.BufferedReader;
	import java.io.IOException;
	import java.io.InputStreamReader;
	import java.util.StringTokenizer;
	public class FlowerRoad {
	/**
	* 백준 14620 꽃길 (https://www.acmicpc.net/problem/14620)
	*/
	private static int n;
	private static int[][] map;
	private static boolean[][] visit;
	private static int[] dx = {-1, 0, 1, 0};
	private static int[] dy = {0, 1, 0, -1};
	private static int result = Integer.MAX_VALUE;
	public static void main(String[] args) throws IOException {
	//꽃 심고 1년후에 꽃이 핀다.
	//다음해 식목일부터 꽃길을 걸을 수 있다.
	//씨앗 3개뿐이 없음
	//세 개의 꽃이 하나도 안죽고 1년후에 만개하길 원한다.
	//n*n
	//꽃이 핀 후 다른 꽃잎과 닿게 될 경우 모두 죽음
	//최소비용
	BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
	n = Integer.parseInt(reader.readLine());
	map = new int[n+1][n+1];
	visit = new boolean[n+1][n+1];
	StringTokenizer st;
	for (int i=1; i<=n; i++) {
	st = new StringTokenizer(reader.readLine());
	for (int j=1; j<=n; j++) {
	map[i][j] = Integer.parseInt(st.nextToken());
	}
	}
	dfs(0, 0);
	System.out.println(result);
	}
	private static void dfs(int count, int sum) {
	if (count == 3) {
	//꽃 3개
	result = Math.min(result, sum);
	} else {
	for (int i=2; i<n; i++) {
	for (int j=2; j<n; j++) {
	if (!visit[i][j] && check(i,j)) {
	visit[i][j] = true;
	int hap = sum(i,j);//꽃 합
	dfs(count+1, sum + hap);
	visitClear(i,j);
	visit[i][j] = false;
	}
	}
	}
	}
	}//bfs
	private static boolean check(int x, int y) {
	for (int i=0; i<dx.length; i++) {
	int nx = x + dx[i];
	int ny = y + dy[i];
	if (visit[nx][ny]) {
	return false;
	}
	}
	return true;
	}//check
	private static void visitClear(int x, int y) {
	for (int i=0; i<dx.length; i++) {
	int nx = x + dx[i];
	int ny = y + dy[i];
	visit[nx][ny] = false;
	}
	}//visitClear
	private static int sum(int x, int y) {
	int hap = map[x][y];
	for (int i=0; i<dx.length; i++) {
	int nx = x + dx[i];
	int ny = y + dy[i];
	visit[nx][ny] = true;
	hap += map[nx][ny];
	}
	return hap;
	}//sum
	}

view raw FlowerRoad.java hosted with ❤ by GitHub

 

 

 

고려할 점

1. 완전탐색

2. 백트래킹