백준 14620 🌸꽃길 : 완전탐색

문제

https://www.acmicpc.net/problem/14620

예제 입력
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

풀이

1. 입력 처리

N과 arr 2차원 배열에 화단 가격 입력 받기

		int N = sc.nextInt();

		int[][] arr = new int[N][N];

		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				arr[i][j] = sc.nextInt();
			}
		}

2. 방문 배열 생성

이미 꽃을 심은 자리에는 꽃을 심을 수 없으므로, 꽃을 심은 자리를 표시하기 위한 2차원 배열 visited를 생성한다.

boolean 배열로 생성하여 꽃을 심었으면 true, 심지 않았으면 false로 나타낸다.

		boolean[][] visited = new boolean[N][N];

3. 최소 비용 변수 설정

매우 큰 값으로 초기화

		int minPrice = 100000;

4. ⭐️핵심로직

세 개의 꽃을 심는 모든 경우의 수 탐색 → 삼중 for문 (실제로는 2차원 배열이므로 6중 for문 느낌)

꽃을 심을 때:

canPlant 메서드로 해당 위치에 심을 수 있는지 검사

심을 수 있으면 visited를 true로 변경

다음 꽃 탐색 후, 탐색이 끝나면 false로 복구 (백트래킹)

		// 세 개의 씨앗을 심기 위한 2차원 배열 삼중 for
		for (int i = 1; i < N - 1; i++) {
			for (int j = 1; j < N - 1; j++) {
				// 꽃을 심을 수 없다면 continue
				if (!canPlant(i, j, visited, N))
					continue;
				// 꽃을 심은 자리는 visited 배열에 true 해주기
				visited[i][j] = true;
				visited[i + 1][j] = true;
				visited[i - 1][j] = true;
				visited[i][j + 1] = true;
				visited[i][j - 1] = true;
                
				//...
                //복구
                visited[i][j] = false;
				visited[i + 1][j] = false;
				visited[i - 1][j] = false;
				visited[i][j + 1] = false;
				visited[i][j - 1] = false;

5.심을 수 있는지 검사 : canPlant

꽃이 피는 자리를 탐색하기 위해 델타를 이용해서 해당 자리를 탐색한다.

꽃이 차지할 5칸이 범위 밖이거나, 이미 다른 꽃이 심겨 있으면 false.

	// 꽃 심는 범위 -> 델타를 활용한 이동
	static int[] di = { 0, 1, -1, 0, 0 };
	static int[] dj = { 0, 0, 0, 1, -1 };

	// 꽃을 심을 수 있는지 검사
	private static boolean canPlant(int x, int y, boolean[][] visited, int N) {
		for (int k = 0; k < 5; k++) {
			int nx = x + di[k];
			int ny = y + dj[k];
			// 범위를 벗어나면 안된다.
			if (nx < 0 || nx >= N || ny < 0 || ny >= N)
				return false;
			// 이미 방문한 곳이면 안된다.
			if (visited[nx][ny])
				return false;
		}
		return true;
	}

6. 꽃 비용 계산 (plantCost)

중심과 상하좌우 4칸의 가격을 합산

	// 꽃의 가격 구하기
	private static int plantCost(int x, int y, int[][] arr) {
		int sum = 0;
		for (int k = 0; k < 5; k++) {
			sum += arr[x + di[k]][y + dj[k]];

		}
		return sum;
	}

7. 최소 비용 갱신

세 번째 꽃을 심었을 때 총 비용 계산 후 minPrice 갱신

// 3개의 씨앗 값 구하기
int cost = plantCost(i, j, arr) + plantCost(x, y, arr) + plantCost(r, c, arr);

//현재 가격 vs minPrice 중에 최솟값 구하기 업데이트하기
minPrice = Math.min(minPrice, cost);

전체코드

package algorithmstudy;

import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Arrays;
import java.util.Scanner;

public class 꽃길 {

	// 꽃 심는 범위 -> 델타를 활용한 이동
	static int[] di = { 0, 1, -1, 0, 0 };
	static int[] dj = { 0, 0, 0, 1, -1 };

	// 꽃을 심을 수 있는지 검사
	private static boolean canPlant(int x, int y, boolean[][] visited, int N) {
		for (int k = 0; k < 5; k++) {
			int nx = x + di[k];
			int ny = y + dj[k];
			// 범위를 벗어나면 안된다.
			if (nx < 0 || nx >= N || ny < 0 || ny >= N)
				return false;
			// 이미 방문한 곳이면 안된다.
			if (visited[nx][ny])
				return false;
		}
		return true;
	}

	// 꽃의 가격 구하기
	private static int plantCost(int x, int y, int[][] arr) {
		int sum = 0;
		for (int k = 0; k < 5; k++) {
			sum += arr[x + di[k]][y + dj[k]];

		}
		return sum;
	}

	public static void main(String[] args) throws FileNotFoundException {
		System.setIn(new FileInputStream("algorithmstudy/src/input.txt"));
		Scanner sc = new Scanner(System.in);

		int N = sc.nextInt();

		int[][] arr = new int[N][N];

		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				arr[i][j] = sc.nextInt();
			}
		}

		// 이미 심은 자리를 표시하기 위한 visited 배열
		// boolean 배열의 기본값은 false
		boolean[][] visited = new boolean[N][N];

		// 최소가격을 저장하기 위한 변수
		// 초기값은 아주 큰 수로 지정하기
		int minPrice = 100000;

		// 세 개의 씨앗을 심기 위한 2차원 배열 삼중 for
		for (int i = 1; i < N - 1; i++) {
			for (int j = 1; j < N - 1; j++) {
				// 꽃을 심을 수 없다면 continue
				if (!canPlant(i, j, visited, N))
					continue;
				// 꽃을 심은 자리는 visited 배열에 true 해주기
				visited[i][j] = true;
				visited[i + 1][j] = true;
				visited[i - 1][j] = true;
				visited[i][j + 1] = true;
				visited[i][j - 1] = true;

				for (int x = 1; x < N - 1; x++) {
					for (int y = 1; y < N - 1; y++) {

						// 꽃을 심을 수 없다면 continue
						if (!canPlant(x, y, visited, N))
							continue;
						// 꽃을 심은 자리는 visited 배열에 true 해주기
						visited[x][y] = true;
						visited[x + 1][y] = true;
						visited[x - 1][y] = true;
						visited[x][y + 1] = true;
						visited[x][y - 1] = true;

						for (int r = 1; r < N - 1; r++) {
							for (int c = 1; c < N - 1; c++) {
								// 꽃을 심을 수 없다면 continue
								if (!canPlant(r, c, visited, N))
									continue;
								// 꽃을 심은 자리는 visited 배열에 true 해주기
								visited[r][c] = true;
								visited[r + 1][c] = true;
								visited[r - 1][c] = true;
								visited[r][c + 1] = true;
								visited[r][c - 1] = true;

								// 3개의 씨앗 값 구하기
								int cost = plantCost(i, j, arr) + plantCost(x, y, arr) + plantCost(r, c, arr);
								
								//현재 가격 vs minPrice 중에 최솟값 구하기 업데이트하기
								minPrice = Math.min(minPrice, cost);
								
								//세번째 꽃 복구
								visited[r][c] = false;
								visited[r + 1][c] = false;
								visited[r - 1][c] = false;
								visited[r][c + 1] = false;
								visited[r][c - 1] = false;
							}

						}
						//두번째 꽃 복구 
						visited[x][y] = false;
						visited[x + 1][y] = false;
						visited[x - 1][y] = false;
						visited[x][y + 1] = false;
						visited[x][y - 1] = false;

					}
				}
				visited[i][j] = false;
				visited[i + 1][j] = false;
				visited[i - 1][j] = false;
				visited[i][j + 1] = false;
				visited[i][j - 1] = false;
			}

		}

		System.out.println(minPrice);

	}

}