[백준 Java] 14620번 꽃길 (브루트포스, DFS, 백트래킹)

 

[Silver II] 꽃길 - 14620

문제 링크

성능 요약

메모리: 15968 KB, 시간: 132 ms

분류

브루트포스 알고리즘

문제 설명

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)이 주어진다.

출력

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

 

💡 나의 접근

접근 : 10 min  / 구현 : 50 min

이었으나... 접근은 틀린 접근이었다.... 도륵... 틀렸는지 아님 엣지케이스가 있었는지 모르겠지만 자주 사용했던 dfs가 바로 떠오르지 않았다.. ㅠ 다른 사람 풀이보고 dfs로 접근했더니 바로 풀린 문제!

1. 압축

좌측은 입력받은 값 map 이고 우측은 중심 + 사방을 더해 만든 priceMap 이다.

각 좌표 씨를 심을 때 5평에 대해서 내야하는 값을 저장해둔 배열이다.

 

만든 priceMap을 가지고 dfs 를 하였다.

심을 씨의 개수는 3개이기 때문에 dfs의 깊이는 3으로 제한하였다.]

 

2. dfs

 0 ) 초기화

visited 배열을 boolean으로 선언하였다.

  1) cnt : 0 (깊이)

'

  cnt가 0일때 for문 안에서  좌측의 priceMap을 탐색하게 되는데 아직 아무곳도 방문하지 않았으므로 제일 처음에 탐색하는 곳을 방문처리하게 된다.

이때 넘겨주는 sum 인자 값은 3이 된다.

 

2 ) cnt : 1 

 다음 재귀를 들어가게 되면 3은 이미 방문 했으니  continue 되어지고 6은 꽃잎이 겹치니 또 continue 로 넘어간다.

다음 7도 꽃잎이 겹쳐 for문에서 넘어가고 

 두번째 7에서 꽃입이 겹치지 않으므로 7에 꽃씨를 심고 다음 깊이로 들어가게 된다.

이때 넘겨주는 sum 값은 10이 된다.

 

  3 ) cnt : 2

  위 사진에서 본것 처럼 cnt가 2일때 이중 for문에서 탐색하여 꽃잎, 꽃술이 겹치지 않는 곳을 찾는다.

여기서는 22 가 된다. 이후 다시 cnt +1 하고 sum은 22를 더해 32가 되어 넘겨주며 재귀로 들어가게 된다.

 

 4 ) cnt : 3

 주어진 꽃씨를 다 심었으므로 종료조건에 해당하게 되며 지금까지 찾은 최소 대여 비용 (cost)와 sum 과 비교하여 

더 작다면 갱신하고 return 하게 된다.

여기서는 cost가 32로 갱신된다.

 

5 )  cnt : 2

 return에 의해서 cnt가 2인 상태의 이중 for문을 마저 돌게 된다.

 

 

 

돌면서 위와 같이 꽃씨를 3개 다 뿌린다면 갱신하고 다시 cnt :2로 돌아온다.

 

6 )  cnt : 1

for문을 다 돌게 되면 그 함수의 코드 실행이 마치게 되어 return 되어지고 cnt 가 1인 상태 즉 씨를 한개만 뿌린 상태로 돌아오게 된다. 

 그 상태에서 for문을 마저 돌때 다음에 들어갈 씨를 뿌릴 곳은4가 된다.

 

이후 똑같이 cnt : 2 상태로 세번째 씨를 뿌리고.. 갱신해주고 

모든 상태를 다 돌게 되면 최소 비용을 찾을  수 있다. 

 

💡 코드

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

public class Main_14620 {
	// 접근 : 10 min
	// 구현 : 50 min
	static int N;
	static int map[][];
	static int priceMap[][]; // i,j를 중심으로한 5평의 가격
	static int cost = Integer.MAX_VALUE; // 꽃을 심기 위한 최소 비용
	static boolean visited[][];
	static int dir[][] = { { 0, 0 }, { 0, 1 }, { 0, -1 }, { 1, 0 }, { -1, 0 } };

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());

		map = new int[N][N];
		for (int i = 0; i < N; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			for (int j = 0; j < N; j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		// ----입력

		priceMap = new int[N][N];
		for (int i = 1; i < N - 1; i++) {
			for (int j = 1; j < N - 1; j++) {
				priceMap[i][j] = getPrice(i, j); // i,j를 기준으로 가운데 + 사방의 금액을 합한 금액
			}
		}

		visited = new boolean[N][N];

		dfs(0, 0);

		System.out.println(cost);

	}

	// cnt : 깊이 -> 씨를 3개 심을 거니까 깊이는 3까지
	private static void dfs(int cnt, int sum) {
		// cnt ==3이기 전에 이미 세 대여 합계가 지금까지 찾은 최소비용을 넘어간다면 자르기
		if (cost <= sum)
			return;

		if (cnt == 3) {
			if (cost > sum) {
				cost = sum;
				return;

			}

			for (int i = 1; i < N - 1; i++) {
				Loop1: for (int j = 1; j < N - 1; j++) {

					if (visited[i][j])
						continue;

					for (int d = 0; d < 5; d++) { // 꽃잎이 닿게 되는 경우
						if (visited[i + dir[d][0]][j + dir[d][1]]) {
							continue Loop1;
						}
					}

					// 이미 씨가 있는 곳과 꽃잎이 닿지 않게 되는 경우 씨를 뿌림
					// 씨를 중심으로 사방에 방문 처리
					for (int d = 0; d < 5; d++) {
						visited[i + dir[d][0]][j + dir[d][1]] = true;
					}

					dfs(cnt + 1, sum + priceMap[i][j]);
					
					//백트래킹 - 원래상태로 돌려 놓기
					for (int d = 0; d < 5; d++) {
						visited[i + dir[d][0]][j + dir[d][1]] = false;
					}

				}
			}
		}
	}

	static int getPrice(int i, int j) {
		int sum = 0;
		for (int d = 0; d < 5; d++) {
			sum += map[i + dir[d][0]][j + dir[d][1]];
		}
		return sum;
	}

}