[백준] 14620번: 꽃길 (Java)

1. 문제설명

씨앗은 꽃을 심고나면 1년 후에 꽃이 핀다. 꽃의 씨앗은 세 개밖에 없으므로 세 개의 꽃이 하나도 죽지 않고 1년 후에 꽃잎이 만개하게 한다. 꽃밭은 N*N의 격자 모양이고 씨앗은 (1,1)~(N,N)의 지점 중 한 곳에 심을 수 있으며 꽃이 피면 격자 모양의 위치를 차지한다. 꽃은 다른 꽃잎 또는 꽃술과 닿게 될 경우 두 꽃 모두 죽고, 화단 밖으로 나갈 경우도 꽃이 죽게 된다.

화단의 지점 당 가격이 주어지고, 세 개의 씨앗이 모두 꽃이 피게 하는 최소 비용을 구하는 문제이다.

• 시간 제한: 2초
• 메모리 제한: 256MB

 

2. 접근 방식

• DFS를 사용하여 3개의 꽃을 심을 수 있는 위치를 탐색한다.
• 꽃을 심을 위치를 선택할 때, 꽃과 꽃잎이 차지하는 위치를 방문하지 않았는지 확인한다.
• 만약 3개의 꽃을 모두 심었다면, 해당 비용(`cost`)를 `minCost` 와 비교하여 최솟값을 갱신한다.
• 꽃을 심은 후, 다른 가능한 위치를 탐색하기 위해 `visited`배열을 원상복구한다. (백트래킹)

 

 

3. 최종 코드

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

public class Main {
    static int n; // 정원의 크기
    static int[][] garden; // 정원의 비용 정보 저장
    static boolean[][] visited; // 방문 여부 확인
    static int minCost = Integer.MAX_VALUE; // 최소 비용 저장

    // 상하좌우
    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};
    
    static void dfs(int flower, int cost) {
        if(flower == 3) { // 꽃을 3개 심은 경우
            if(cost < minCost) // 최소 비용 갱신
                minCost = cost;
            return;
        }

        // (2, 2)부터 (n-1, n-1)까지 탐색
        for(int i=2; i<n; i++) {
            for(int j=2; j<n; j++) {
                boolean check1 = true;
                for(int a=0; a<4; a++) {
                    int nx = i + dx[a];
                    int ny = j + dy[a];
                    // 현재 위치와 상하좌우 위치가 방문 가능한지 확인
                    if (visited[nx][ny] || visited[i][j])
                        check1 = false;
                }

                if(check1) { // 방문 가능하면
                    boolean check = false;
                    visited[i][j] = true; // 현재 위치 방문 처리
                    int c = garden[i][j]; // 현재 위치 비용

                    // 상하좌우 위치의 방문 처리 및 비용 계산
                    for(int a=0; a<4; a++) {
                        int nx = i + dx[a];
                        int ny = j + dy[a];
                        if(!visited[nx][ny]) {
                            check = true;
                            visited[nx][ny] = true;
                            c += garden[nx][ny];
                        }
                    }

                    if(check) { // 씨앗을 심을 수 있는 위치이면
                        dfs(flower+1, cost+c); // 다음 꽃 심기
                    }

                    // 방문 처리 원상 복구 (백트래킹)
                    visited[i][j] = false;
                    for(int a=0; a<4; a++) {
                        int nx = i + dx[a];
                        int ny = j + dy[a];
                        visited[nx][ny] = false;
                    }
                }

            }
        }
        
    }

    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+1][n+1];
        visited = new boolean[n+1][n+1];
        for(int i=1; i<=n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for(int j=1; j<=n; j++) {
                // 비용 정보 저장
                garden[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        dfs(0, 0);
        System.out.println(minCost);
    }
}