백준 - 꽃길

본 알고리즘 풀이는 Routine Study에서 진행하고 있습니다.
저를 포함한 구성원이 대부분 초보이므로, 원하시는분은 언제라도 들어오셔도 좋습니다.

문의는 댓글 바람.

문제 출처 : https://www.acmicpc.net/problem/14620

[문제 설명]

땅에 꽃을 3개 부화시킬려고한다. 가장 돈이 적게 들게 땅을 사는 방법은?

[접근 방법]

완전탐색 문제다. 꽃은 왼쪽 오른쪽 위 아래 크기이기 때문에, 1~땅의 크기-1까지 놓을 수 있다.

땅의 크기가 6이상 10이하이므로 면적은 최소 36에서 100이 된다.

시간복잡도는 꽃을 심을 때마다 면적을 전부 검색하며, 꽃의 개수는 3개이므로  O(면적^3)

땅의 크기를 N으로 줬을 때, 면적은 N^2이니 O(면적^3)은 O(N^6)이 된다.

언뜻 보기엔 N^6이므로 시간이 오래 걸릴 듯 하지만, N의 최대값은 10이므로 10^6 -> 100만이 최대 연산 횟수이다.

 

[수정 전 코드]

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

public class Main {
    // 맵의 가로 길이
    static int length;
    // 가격이 적혀있는 맵
    static int[][] mapOfPrice;
    // 꽃과 잎이 심어져 있는 곳.
    static boolean[][] visited;
    // 최소 비용
    static int pee = Integer.MAX_VALUE;
    public static void main(String[] args) throws IOException {
        // 입력
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        length = Integer.parseInt(br.readLine());
        mapOfPrice = new int[length][length];
        visited = new boolean[length][length];
        for (int row = 0; row < length; row++) {
            StringTokenizer record = new StringTokenizer(br.readLine()," ");
            for (int column = 0; column < length; column++) {
                mapOfPrice[row][column] = Integer.parseInt(record.nextToken());
            }
        }

        recursion(0, 0);
        System.out.println(pee);
    }

    private static void recursion(int numOfPlantedFlower, int currentCost) {
        if (numOfPlantedFlower == 3) {
            pee = Math.min(pee,currentCost);
            return;
        }

        for (int row = 1; row <= length-2; row++) {
            for (int column = 1; column <= length-2; column++) {
                boolean isPlantSuccess = plantHere(row,column);
                if (isPlantSuccess) {
                    numOfPlantedFlower++;
                    recursion(numOfPlantedFlower, currentCost+getCost(row,column));

                    deleteHere(row,column);
                    numOfPlantedFlower--;
                } else {
                    continue;
                }
            }
        }
    }

    private static int getCost(int row, int column) {
        return mapOfPrice[row][column]+mapOfPrice[row-1][column]+mapOfPrice[row+1][column]+mapOfPrice[row][column-1]+ mapOfPrice[row][column+1];
    }

    private static boolean isOnTheGround(int row, int column) {
        if ((1<=row && row<=length-2 && 1<=column && column<=length-2)) {
            return true;
        }

        return false;
    }
    private static boolean isFlowerHere(int row, int column) {
        if (visited[row][column] || visited[row-1][column] ||  visited[row+1][column] || visited[row][column-1] || visited[row][column+1] || visited[row][column]) {
            return true;
        }

        return false;
    }

    private static boolean plantHere(int row,int column) {
        // 맵위가 아니거나 꽃이 있으면 return false
        if (!isOnTheGround(row,column) || isFlowerHere(row,column)) {
            return false;
        }

        visited[row][column] = true;
        visited[row-1][column] = true;
        visited[row+1][column] = true;
        visited[row][column-1] = true;
        visited[row][column+1] = true;
        return true;
    }

    private static boolean deleteHere(int row, int column) {
        // 맵 위가 아니거나 꽃이 없으면
        if (!isOnTheGround(row,column) || !isFlowerHere(row,column)) {
            return false;
        }

        visited[row][column] = false;
        visited[row-1][column] = false;
        visited[row+1][column] = false;
        visited[row][column-1] = false;
        visited[row][column+1] = false;
        return true;
    }
}

일단 코드가 엄청 더럽다. 일단 생각나는대로 짠 코드인데 불필요한 코드가 많아 보인다.

 

[수정 후 코드]

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

public class Main {
    static int length;
    static int[][] mapOfPrice;
    static boolean[][] visited;
    static int pee = Integer.MAX_VALUE;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        length = Integer.parseInt(br.readLine());
        mapOfPrice = new int[length][length];
        visited = new boolean[length][length];
        for (int row = 0; row < length; row++) {
            StringTokenizer record = new StringTokenizer(br.readLine()," ");
            for (int column = 0; column < length; column++) {
                mapOfPrice[row][column] = Integer.parseInt(record.nextToken());
            }
        }

        getLandPrice(0, 0);
        System.out.println(pee);
    }

    private static void getLandPrice(int numOfPlantedFlower, int currentCost) {
        if (numOfPlantedFlower == 3) {
            pee = Math.min(pee,currentCost);
            return;
        }

        for (int row = 1; row <= length-2; row++) {
            for (int column = 1; column <= length-2; column++) {
                if (!isFlowerHere(row,column)) {
                    plantOrRemove(row,column);
                    numOfPlantedFlower++;
                    getLandPrice(numOfPlantedFlower, currentCost+getCost(row,column));

                    plantOrRemove(row,column);
                    numOfPlantedFlower--;
                }
            }
        }
    }

    private static int getCost(int row, int column) {
        return mapOfPrice[row][column]+mapOfPrice[row-1][column]+mapOfPrice[row+1][column]+mapOfPrice[row][column-1]+ mapOfPrice[row][column+1];
    }

    private static boolean isFlowerHere(int row, int column) {
        if (visited[row][column] || visited[row-1][column] ||  visited[row+1][column] || visited[row][column-1] || visited[row][column+1]) {
            return true;
        }

        return false;
    }

    private static void plantOrRemove(int row,int column) {
        visited[row][column] = !visited[row][column];
        visited[row-1][column] = !visited[row-1][column];
        visited[row+1][column] = !visited[row+1][column];
        visited[row][column-1] = !visited[row][column-1];
        visited[row][column+1] = !visited[row][column+1];
    }
}

가로 세로 인덱스는 어차피 for문에서 제한을 제대로 줬으므로 딱히 인덱스가 맵 위에 있는지 체크할 필요가 없었다.