[BAEKJOON] 14620. 꽃길(JAVA)

:D 문제

---

문제

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

출력

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

Baekjoon

14620번: 꽃길

 

 

:D 풀이 방법

---

나는 dfs를 통해 문제를 해결하였다. 3개의 씨앗을 심을 수 있기 때문에 인자로 cnt와 비용의 합을 넘겨주었다.

탐색 범위는 1부터 N-1까지 진행하였다.(시작 0으로 설정) 그 이유는 아래 왼쪽 그림과 같이 꽃을 가장자리에 심을 경우, 

화단 범위를 벗어나기 때문이다. 그래서 오른쪽 그림처럼 화단의 가장자리를 제외하고 탐색을 진행하였다.

 

 

:D 작성 코드

---

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

public class Solution14620H {

    static int[][] garden; // 화단
    static int[][] dir = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; // 상 - 하 - 좌 - 우
    static boolean[][] isSelected;
    static int N, minCost = Integer.MAX_VALUE;

    public static void main(String[] args) throws IOException {

        // 입력
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        garden = new int[N][N];
        isSelected = new boolean[N][N];

        // 가든 생성
        for (int line = 0; line < N; line++) {
            StringTokenizer st = new StringTokenizer(br.readLine(), " ");
            for (int i = 0; i < N; i++) {
                garden[line][i] = Integer.parseInt(st.nextToken());
            }
        }

        // 탐색 시작
        dfs(0, 0);
        System.out.print(minCost);
    }

    // dfs 탐색
    private static void dfs(int cnt, int cost) {

        // 세 개의 씨앗을 다 심었다면 비용 비교
        if (cnt == 3) {
            minCost = Math.min(minCost, cost);
            return;
        }

        // 꽃잎이 밖으로 나가면 죽게 됨으로 1부터 N-1까지 탐색
        for (int x = 1; x < N - 1; x++) {
            for (int y = 1; y < N - 1; y++) {

                // 이미 선택이 됐거나 꽃잎이 겹친다면 진행 x
                if (!isPossible(x, y)) continue;

                // 현재 위치 및 4방 선택
                isSelected[x][y] = true;
                setSelection(x, y, true);

                // 다음 위치 탐색
                dfs(cnt + 1, cost + calcCost(x, y));

                // 탐색 후, 선택 해제
                isSelected[x][y] = false;
                setSelection(x, y, false);
            }
        }
    }

    // 현재 위치를 중심으로 꽃을 심을 수 있는지 검사
    private static boolean isPossible(int x, int y) {

        if(isSelected[x][y]) return false;

        for (int i = 0; i < 4; i++) {
            int nx = x + dir[i][0];
            int ny = y + dir[i][1];

            // 이미 선택된 영역(겹친 꽃잎)이 있다면 현재 위치 선택 할 수 없음으로 false
            if (isSelected[nx][ny]) return false;
        }
        return true;
    }

    // flag에 따라 선택 여부 설정
    private static void setSelection(int x, int y, boolean flag){

        for (int i = 0; i < 4; i++) {
            int nx = x + dir[i][0];
            int ny = y + dir[i][1];
            isSelected[nx][ny] = flag;
        }
    }

    // 현재 위치 + 4방의 비용 계산
    private static int calcCost(int x, int y) {

        int costs = garden[x][y];
        for (int i = 0; i < 4; i++) {
            int nx = x + dir[i][0];
            int ny = y + dir[i][1];
            costs += garden[nx][ny];
        }
        return costs;
    }
}

 

 

 

마무리

처음에 문제를 잘못 이해하서 다르게 풀다가 계속 틀렸다.. 진짜ㅠㅠㅠㅠ

문제 좀 잘 보자아아!!