알고리즘 | 백트래킹 | Java 백준[Silver II] 꽃길 - 14620

[Silver II] 꽃길 - 14620

문제 링크

성능 요약

메모리: 15184 KB, 시간: 108 ms

분류

브루트포스 알고리즘

제출 일자

2024년 9월 27일 21:13:56

문제 설명

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

출력

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

풀이

이 문제는 모든 좌표에 꽃을 심어보고 가장 적은 비용을 찾는 방식으로 풀어보고자 했습니다.
이때 조건 없이 모든 과정을 탐색하게 되면 화단의 한 변의 최대 길이가 10이므로 꽃을 심을 수 있는 좌표만 계산했을 때 약 (10 - 2) * (10 -2) = 64,64에서 3개를 뽑는 조합을 생각해봤을 때 41,664개의 경우의 수가 나오게 됩니다. 이를 모두 확인하는 것은 시간 낭비이므로 불필요한 경우를 줄일 수 있도록 백트래킹을 적용할 것입니다.

조건을 적용하기 위해서 현재까지 가장 저렴한 금액을 기록하고 그 값보다 큰 값일 때, 꽃의 개수가 3개일 때까지 DFS의 depth를 증가시켜 탐색하게 됩니다.

전체 코드

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

public class Main {

    private static final int TOTAL_FLOWER_COUNT = 3;
    private static final int[] dx = {0, 0, -1, 1};
    private static final int[] dy = {-1, 1, 0, 0};
    private static int answer = Integer.MAX_VALUE;
    private static int[][] flowerBedCost;
    private static boolean[][] visited;
    private static int length;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        length = Integer.parseInt(br.readLine());

        flowerBedCost = new int[length][length];
        visited = new boolean[length][length];
        StringTokenizer st;
        for (int i = 0; i < length; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            for (int j = 0; j < length; j++) {
                flowerBedCost[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        DFS(0, 0);
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        bw.write(String.valueOf(answer));
        bw.flush();
        bw.close();
    }

    static void DFS(int depth, int sum) {
        if (sum >= answer) {
            return; // 현재까지의 합이 이미 최소 비용보다 크면 종료
        }

        if (depth == TOTAL_FLOWER_COUNT) { // 문제상 종료 조건
            answer = Math.min(sum, answer);
        } else {
            // 각 위치를 탐색하여 꽃을 심기
            for (int y = 1; y < length - 1; y++) {
                for (int x = 1; x < length - 1; x++) {
                    if (isNotVisited(x, y)) {
                        int cost = calculateCost(x, y);
                        DFS(depth + 1, sum + cost);
                        clearVisit(x, y);
                    }
                }
            }
        }
    }

    static boolean isNotVisited(int x, int y) {
        // 꽃의 주변 위치가 방문된 상태인지 확인
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            if (visited[ny][nx]) {
                return false; // 주변에 이미 심어진 꽃이 있는 경우
            }
        }
        return true; // 심을 수 있는 경우
    }

    static int calculateCost(int x, int y) {
        int currentCost = flowerBedCost[y][x];
        visited[y][x] = true; // 현재 위치 방문 처리
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            currentCost += flowerBedCost[ny][nx]; // 주변 비용 계산
            visited[ny][nx] = true; // 주변 위치 방문 처리
        }
        return currentCost; // 총 비용 반환
    }

    static void clearVisit(int x, int y) {
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            visited[ny][nx] = false; // 방문 기록 초기화
        }
        visited[y][x] = false; // 현재 위치 방문 기록 초기화
    }
}