백준 14620번 꽃길 (java)

[Silver II] 꽃길 - 14620

문제 링크

성능 요약

메모리: 18532 KB, 시간: 204 ms

분류

브루트포스 알고리즘

제출 일자

2024년 3월 24일 20:17:12

문제 설명

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

출력

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

 

풀이

모든 경우의 수를 다 찾아봐야하는 문제이기 때문에 어떤 방식으로 탐색을 하는게 효율적일까 생각하는데 시간을 너무 많이 썼다. 

우선 dfs로 탐색을 하기로 했고, 백트레킹 조건을 (count == 3) count는 꽃의 개수 로 걸었다. 당연한 조건이어서 백트레킹이라 하기에도 애매한 거 같긴하다,,

 

코드

package hello.core.backjoon;

import java.io.*;
import java.util.*;
import java.math.*;
import java.lang.*;

public class Main{
    static int SUM = 20000;
    static int N = 0;
    static int x[][];
    static Boolean exists[][];
    public static void main(String args[])throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        N = Integer.parseInt(br.readLine());

        x = new int[N][N];
        exists = new Boolean[N][N];

        for(int  i = 0 ;i<N;i++){
            StringTokenizer st = new StringTokenizer(br.readLine());
            for(int j  = 0 ;j<N;j++){
                x[i][j] = Integer.parseInt(st.nextToken());
                exists[i][j] = true;
            }
        }

        dfs(0,0);
        System.out.println(SUM);

    }

    public static void dfs(int count, int sum){
        if(count == 3){
            SUM = Math.min(sum, SUM);
            return;
        }

        else{
            for(int i = 1;i<N-1;i++){
                for(int j=1;j<N-1;j++){
                    if(isPossible(i,j)) {
                        int tmp_sum = getSum(i, j);
                        setFalse(i,j);

                        dfs(count+1,sum+tmp_sum);
                        setTrue(i,j);
                    }
                }
            }
        }
    }

    public static Boolean isPossible(int i, int j){
        if(exists[i-1][j] && exists[i+1][j] && exists[i][j-1] && exists[i][j+1]){
            return true;
        }
        else{
            return false;
        }
    }

    public static int getSum(int i,int j){
        return x[i][j] + x[i-1][j] + x[i+1][j] + x[i][j-1] + x[i][j+1];
    }

    public static void setFalse(int i, int j){
        exists[i][j] = false;
        exists[i-1][j] = false;
        exists[i+1][j] = false;
        exists[i][j-1] = false;
        exists[i][j+1] = false;
    }
    public static void setTrue(int i, int j){
        exists[i][j] = true;
        exists[i-1][j] = true;
        exists[i+1][j] = true;
        exists[i][j-1] = true;
        exists[i][j+1] = true;
    }
}