[JAVA] 백준 14620 완전탐색(백트래킹)

 

 

 

14620번: 꽃길

문제

하이테크 앞 화단의 대여 가격은 격자의 한 점마다 다르기 때문에 진아는 서로 다른 세 씨앗을 모두 꽃이 피게하면서 가장 싼 가격에 화단을 대여하고 싶다.

단 화단을 대여할 때는 꽃잎이 핀 모양을 기준으로 대여를 해야하므로 꽃 하나당 5평의 땅을 대여해야만 한다.

돈이 많지 않은 진아를 위하여 진아가 꽃을 심기 위해 필요한 최소비용을 구해주자!

풀이

해당 문제는 꽃의 씨앗을 심은 기준으로 상, 하, 좌, 우, 현재 위치가 다른 꽃들과 겹치지 않도록 심으면서, 토지료 (땅값)이 최소가 되게 하라는 문제였다.

처음에는 완전탐색으로 땅값이 최소가 되는 위치를 선택하면서 선택한 위치와 상하좌우의 가격을 최대치로 올려서 선택되지 않도록 접근했지만, 문제도 풀리지 않았고 항상 최소값을 선택한다고 하더라도 전체가 최소가 되는 것은 아니라는 생각이 자꾸 들었기 때문에 다른 접근을 해야만 했다.

풀이법을 찾아보다보니 백트래킹이라는 완전탐색 기법이 존재했고 해당 기법으로 접근해서 문제를 해결했다.

백트래킹 기법은 DFS로 모든 경우의 수를 탐색해나가면서 가망이 없는 경우의 수들을 미리 쳐내어 전체를 Brute Force하는 기법보다 더 빠른 시간복잡도를 가질 수 있다.

해당 문제는 다음과 같은 수도코드를 기준으로 해결하였다.

1. 만약 현재 DFS가 현재 발견한 최소 값보다 크다면 DFS를 종료한다. (가망이 없는 경우의 수를 제거한다.)
2. 만약 현재 DFS의 깊이가 3(씨앗을 심은 수)이고 현재 발견한 최소값보다 작다면 값을 갱신하고 종료한다.
3. 만약 현재 DFS의 깊이가 3이 아니라면 모든 경우의 수를 DFS 재귀로 탐색하면서 최솟값을 탐색한다.
   1. 여기서 씨앗을 심어야 하기 때문에 상, 하, 좌, 우, 현재 위치를 방문체크를 한다.

백트래킹 기법이기 때문에 현재 깊이에서 탐색이 종료되면 이전 깊이에서 다른 경우의 수를 찾아나간다.

• 이렇게 다시 되돌아가기 때문에 백트래킹이라고 불리는 것 같다.

이제 코드를 살펴보자.

📌 현재 위치에 심을 수 있는지 여부를 체크한다.

    static boolean checkVisit(int x, int y){
        for(int i=0; i<4; i++){
            if(V[x+dx[i]][y+dy[i]]){
                return false;
            }
        }
        return true;
    }

• 현재 위치를 기준으로 상, 하, 좌, 우를 체크하여 방문한 적이 있는 위치가 있다면 false를 반환한다.

📌 방문하려는 위치를 체크해놓고, 필요한 비용을 반환한다.

    static int sumCost(int x, int y){
        int sum = A[x][y];
        V[x][y] = true;
        for(int i=0; i<4; i++){
            sum += A[x+dx[i]][y+dy[i]];
            V[x+dx[i]][y+dy[i]] = true;
        }
        return sum;
    }

• 현재 위치를 방문해야 하기 때문에 상, 하, 좌, 우, 현재위치의 방문 여부를 true로 설정하고 모든 땅값을 더해 반환한다.

📌 현재 위치의 방문 여부를 다시 초기화한다.

    static void clearVisit(int x, int y){
        for(int i=0; i<4; i++){
            V[x+dx[i]][y+dy[i]] = false;
        }
        V[x][y] = false;
    }

• 현재 위치를 기준으로 상, 하, 좌, 우, 현재 위치의 방문 여부를 false로 설정한다. (백트래킹하기 위함)

📌 모든 메서드를 조합하여 백트래킹 구현

    static void DFS(int depth, int sum){
        // 백트래킹 효율, 더이상 탐색할 필요가 없다면 연산을 종료한다.
        if(sum >= answer) return;

        if(depth == 3){
            answer = Math.min(sum, answer);
        }else{
            for(int i=1; i<N-1; i++){
                for(int j=1; j<N-1; j++){
                    if(!V[i][j] && checkVisit(i, j)){
                        int cost = sumCost(i, j);
                        DFS(depth+1, sum+cost);
                        clearVisit(i, j);
                    }
                }
            }
        }
    }

• 첫 번째 if문은 현재 탐색하려는 경우의 수가 이미 발견된 최솟값을 넘어섯다면 굳이 더 탐색할 필요가 없으므로 탐색을 종료하고 다시 되돌아간다. (백트래킹의 효율이 증가하는 부분, 이 부분을 잘 설정해야 시간 복잡도가 낮아진다.)
• 두 번째 if문은 현재 씨앗을 3개 심었다면 현재 값과 비교하여 최솟값을 갱신한다.
• 만약 3개를 아직 심지 않았다면 1 ~ N-1 (땅 밖으로 꽃이 삐져나가면 꽃이 죽어버린다.)을 탐색한다.
  • 이때 탐색하는 위치는 현재 위치 + 상, 하, 좌, 우의 위치가 이전에 방문한적이 없을 경우다.
  • 토지의 비용과, 현재 위치를 기준으로 상, 하, 좌, 우, 현재 위치의 방문 여부를 체크한다.
  • DFS로 다시 재귀 연산을 진행하는데 씨앗의 개수(depth)를 추가해주고, 현재의 비용을 추가해준다.
  • DFS로 재귀한 후 다시 백트래킹 하기 위해 방문 여부를 다시 초기화해준다.

📌 전체 코드

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

public class Main {
    static int[] dx = {0, 0, 1, -1};
    static int[] dy = {1, -1, 0, 0};
    static int answer = Integer.MAX_VALUE;
    static int[][] A;
    static int N;
    static boolean[][] V;

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

        A = new int[N][N];
        V = new boolean[N][N];

        StringTokenizer st;
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            for (int j = 0; j < N; j++) {
                A[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        DFS(0, 0);
        System.out.println(answer);
    }

    static void DFS(int depth, int sum){
        // 백트래킹 효율, 더이상 탐색할 필요가 없다면 연산을 종료한다.
        if(sum >= answer) return;

        if(depth == 3){
            answer = Math.min(sum, answer);
        }else{
            for(int i=1; i<N-1; i++){
                for(int j=1; j<N-1; j++){
                    if(!V[i][j] && checkVisit(i, j)){
                        int cost = sumCost(i, j);
                        DFS(depth+1, sum+cost);
                        clearVisit(i, j);
                    }
                }
            }
        }
    }

    static boolean checkVisit(int x, int y){
        for(int i=0; i<4; i++){
            if(V[x+dx[i]][y+dy[i]]){
                return false;
            }
        }
        return true;
    }

    static int sumCost(int x, int y){
        int sum = A[x][y];
        V[x][y] = true;
        for(int i=0; i<4; i++){
            sum += A[x+dx[i]][y+dy[i]];
            V[x+dx[i]][y+dy[i]] = true;
        }
        return sum;
    }

    static void clearVisit(int x, int y){
        for(int i=0; i<4; i++){
            V[x+dx[i]][y+dy[i]] = false;
        }
        V[x][y] = false;
    }
}

결과