백준 14620 - 꽃길

Java

14620 번 - 꽃길

문제

접근 방법

보통 백트래킹으로 해결하지만, 조합으로 3개의 숫자를 뽑고 그 수를 좌표로 반환하여 화단에 꽃을 놓아보는 방식으로 해결하였다.

DFS의 조합을 통해 0부터 (n-2)^2 까지의 수 중에서 3개를 뽑는다.

(n-2)^2인 이유는 꽃의 중심점을 화단의 끝에다 두면 꽃을 필 수가 없기 때문이다.
문제의 화단의 크기는 6*6이므로, 0 ~ 4*4까지의 수를 3개 뽑는다.

이후 뽑은 3개의 수를 좌표로 변환한다.

0  1  2  3
4  5  6  7
8  9  10 11
12 13 14 15

예를들어, [0, 5, 11]을 뽑았으면 {[0,0], [1,1], [2,3]} 가 된다.

뽑은 3개의 점을 화단에 놓고 [상,하,좌,우] 꽃을 두어 서로 안겹치는지 확인하고,
겹치지 않으면 해당 위치의 화단 가격을 계산한다.

이후 계산한 값의 최소를 구한다.

코드

import java.util.*;
import java.io.*;

public class Main {
	static int n, m, m2, result;
	static int[][] price;
	static int[] sel;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer stk;
    	n = stoi(br.readLine());
    	m = n - 2;
    	m2 = (int)Math.pow(m, 2);

    	price = new int[n][n];
    	sel = new int[3];

    	for(int i = 0; i < n; i++) {
    		stk = new StringTokenizer(br.readLine());
    		for(int j = 0; j < n; j++) {
    			price[i][j] = stoi(stk.nextToken());
    		}
    	}
    	result = Integer.MAX_VALUE;

    	DFS(0,0);

    	System.out.println(result);
    	br.close();
	}

	// 꽃을 놓을 수 있는 중심점 3곳을 뽑는다.
	private static void DFS(int lv, int st) {
		if(lv == 3) {
			int rt = chkValid();
			if(rt != -1) {	// -1이 아니면 화단에 꽃을 놓아 그 금액이 반환되었다는 뜻이다
				result = Math.min(result, rt);
			}
			return;
		}

		for(int i = st; i < m2; i++) {
			sel[lv] = i;
			DFS(lv + 1, i + 1);
		}
	}

	static int[] yArr = new int[3];
	static int[] xArr = new int[3];
	static boolean[][] putFwr;
	// 세 점에 꽃을 놓을 수 있는지 판단
	private static int chkValid() {
		// 구한 3점의 y,x 좌표를 구한다
		for(int i = 0; i < 3; i++) {
			yArr[i] = sel[i] / m;
			xArr[i] = sel[i] % m;
		}

		putFwr = new boolean[n][n];
		int y,x,ny,nx;

		int dy[] = new int[] {-1,1,0,0};
		int dx[] = new int[] {0,0,-1,1};

		for(int i = 0; i < 3; i++) {
			y = yArr[i] + 1;
			x = xArr[i] + 1;

			// 만약 꽃을 놓으려는 지점에 이미 꽃이 있으면
			if(putFwr[y][x] == true)
				return -1;
			putFwr[y][x] = true;

			// 꽃 중심에서 상하좌우 꽃을 놔둔다
			for(int j = 0; j < 4; j++) {
				ny = y + dy[j];
				nx = x + dx[j];

				if(putFwr[ny][nx] == true)
					return -1;
				putFwr[ny][nx] = true;
			}
		}

		// 여기까지 온 것이면 3개의 꽃을 놓았다는 것
		int sum = 0;
		// 꽃을 심은 화단의 가격을 계산
		for(int i = 0; i < n; i++) {
			for(int j = 0; j < n; j++) {
				if(putFwr[i][j]) {
					sum += price[i][j];
				}
			}
		}

		return sum;
	}

	static int stoi(String str) {
    	return Integer.parseInt(str);
    }
}

총평

후기

개선할 점