[백준] 14620 꽃길 (JAVA)

문제 링크:

14620번: 꽃길

 

 

난이도: 실버 2

 

 

문제:

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

 

 

출력:

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

 

문제 이해:

문제 이해는 모두 어렵지 않을 것이라 생각한다. 

 

중심과 상·하·좌·우로 십자 모양의 꽃을 세 송이 심어야 한다. 꽃잎이나 중심이 서로 겹치면 그 자리는 사용할 수 없다. 이렇게 꽃 세 송이를 배치할 수 있는 경우 중 땅값의 합이 최소가 되는 값을 구하면 된다.

 

예제 입력 1을 예를 들어보면 다음과 같이 12가 최소가 되는 것이다.

 

 

구현 방향:

이를 보자마자 떠오른 방법은 완전 탐색이다. 최소 비용을 구하려면 가능한 모든 경우를 확인해야 하므로, 일부 경우를 건너뛰고 답을 구할 수는 없다. 따라서 꽃을 설치할 수 있는 모든 좌표를 대상으로 재귀와 백트래킹을 이용해 탐색하는 방식이 가장 적절하다

.

구체적으로는, 격자의 0행 0열과 같이 테두리 부분은 애초에 꽃을 심을 수 없으므로 제외하고, (1,1)부터 (N-2,N-2)까지 내부 좌표를 중심 후보로 탐색을 시작한다. 각 좌표에 대해 꽃을 설치할 수 없는 경우는 그대로 PASS하고, 설치할 수 있는 경우에는 해당 위치에 꽃을 심은 뒤 재귀적으로 다음 꽃을 배치한다. 재귀 호출이 끝나면 방문한 칸을 원복하여 다른 조합을 탐색할 수 있게 한다.

 

이러한 방식으로 모든 좌표를 훑으며 3송이를 배치한 뒤, 가능한 경우 중 땅값의 합이 가장 작은 값을 찾으면 된다.

 

이를 그대로 코드로 구현하면 다음과 같다.

 

 

정답 코드:

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

public class Main {
    static int N;
    static int[][] matrix;
    static boolean[][] visited;
    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};
    static int minGold = Integer.MAX_VALUE;

    // 꽃을 생성해서 골드를 반환하는 메서드
    //생성할 수 없다면 -1 반환
    public static int makeFlower(int x, int y) {
        int totalGold = matrix[x][y];
        if (visited[x][y]) return -1;
        visited[x][y] = true;

        // 상 하 좌 우 탐색
        for (int d = 0; d < 4; d++) {
            int nx = x + dx[d];
            int ny = y + dy[d];


            // 꽃을 필 수 없는 경우 원복 후 반환
            if (visited[nx][ny]) {
                // 중심 해제
                visited[x][y] = false;

                // 지금까지 방문 처리한 방향만 false
                for (int k = 0; k < d; k++) {
                    int px = x + dx[k];
                    int py = y + dy[k];
                    visited[px][py] = false;
                }
                return -1;
            }
            visited[nx][ny] = true;
            totalGold += matrix[nx][ny];
        }
        return totalGold;
    }

    //꽃 원복 함수
    public static void rollback(int x,int y){
        visited[x][y] = false;
        for (int d = 0; d < 4; d++) {
            int nx = x + dx[d];
            int ny = y + dy[d];
            visited[nx][ny] = false;
        }
    }

    public static void solve(int count, int curGold) {
        if (count == 3) { // 3송이 완성
            minGold = Math.min(minGold, curGold);
            return;
        }
        //이미 골드가 최소 골드보다 많으면 리턴
        if(curGold>minGold) return;

        for (int i = 1; i < N-1; i++) {
            for (int j = 1; j < N-1; j++) {
                int gold = makeFlower(i, j);
                if(gold!=-1){
                    solve(count+1,curGold+gold);
                    // 방금 심은 꽃만 원복
                    rollback(i,j);
                }
            }
        }
    }

    public static void main(String[] args) throws IOException {
        // 초기 세팅
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        matrix = new int[N][N];

        for (int i = 0; i < N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int j = 0; j < N; j++) {
                matrix[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        //초기세팅 끝

        //탐색 시작
        visited = new boolean[N][N];
        solve(0,0);
        System.out.println(minGold);

    }


}

 

 

마무리하며:

처음에는 단순히 재귀만을 이용하여 모든 경우의 수를 탐색하려고 하였다. 하지만 꽃을 놓는 과정에서 조건이 많아지고, 매 단계마다 방문 여부를 복구해야 하는 로직이 얽히다 보니 코드가 지나치게 복잡해졌다. 이로 인해 재귀의 흐름을 따라가는 것 자체가 어려워졌고, 디버깅에도 많은 시간이 걸렸다.

 

이후 접근 방식을 바꿔, 모든 조합은 그대로 탐색하되 반복문(for)과 재귀를 적절히 섞어 사용하는 방식으로 코드를 단순화했다. 반복문으로 탐색할 좌표를 순차적으로 처리하면서, 그 내부에서만 재귀 호출을 돌리는 구조로 바꾸자 코드의 흐름이 훨씬 명확해졌다. 결과적으로 구현이 단순해졌을 뿐 아니라, 디버깅과 이해도 쉬워졌다.

 

이번 경험을 통해, 재귀만이 항상 최선의 답은 아니며 반복문과 적절히 병행하는 것이 오히려 효율적이고 가독성 좋은 코드가 될 수 있다는 점을 배웠다.

 

 

감사합니다.