[BOJ - JAVA] 14620 - 꽃길(브루트포스)

# 주소

https://www.acmicpc.net/problem/14620

14620번: 꽃길

# 문제

# 문제 해설 및 코드 리뷰

import java.util.Scanner;

public class Main {
    static int n;
    static int dx[] = {-1,1,0,0};
    static int dy[] = {0,0,1,-1};
    static int[][] arr;
    static int min = Integer.MAX_VALUE;
    static boolean[][] visit;
    public static void main(String[] args){
        Scanner scan = new Scanner(System.in);
        n = scan.nextInt();
        arr = new int[n][n];
        visit = new boolean[n][n];
        for(int i = 0; i < n; i++){
            for(int j = 0; j < n; j++)
                arr[i][j] = scan.nextInt();
        }
        dfs(0,0);
        System.out.println(min);
    }
    static void dfs(int cnt, int sum){
        if(cnt == 3) {
            min = Math.min(min,sum);
            return;
        }

        for(int i = 1; i < n-1; i++){
            for(int j = 1; j < n-1; j++){
                if(!visit[i][j] && check(i,j)){
                    visit[i][j] = true;
                    dfs(cnt + 1, sum + search(i,j));
                    visitClear(i,j);
                    visit[i][j] = false;
                }
            }
        }
    }
    static boolean check(int x, int y){
        for(int i = 0; i < 4; i++){
            int nx = x + dx[i];
            int ny = y + dy[i];
            if(visit[nx][ny])
                return false;
        }
        return true;
    }
    static void visitClear(int x, int y){
        for(int i = 0; i < 4; i++){
            int nx = x + dx[i];
            int ny = y + dy[i];
            visit[nx][ny] = false;
        }
    }
    static int search(int x, int y){
        int hap = arr[x][y];
        for(int i = 0; i < 4; i++){
            int nx = x + dx[i];
            int ny = y + dy[i];
            visit[nx][ny] = true;
            hap += arr[nx][ny];
        }
        return hap;
    }
}

오랜만입니다.

브루트포스를 일주일간 30개 푼 거 같은데 쉬운 문제라도 어려운게 많네요.

특히 문자열 처리 부분에서 많이 애먹었습니다.

전부 다 리뷰하고 싶지만 그러기엔 너무 많은 시간적 소요가 발생하니.. 괜찮은 문제만 리뷰해보도록 하겠습니다.

14620 - 꽃길 문제는 백트래킹에서 특히 재귀함수를 많이 쓰는 것이 특징이었습니다.

한 번 살펴보겠습니다.

public class Main {
    static int n;
    static int dx[] = {-1,1,0,0};
    static int dy[] = {0,0,1,-1};
    static int[][] arr;
    static int min = Integer.MAX_VALUE;
    static boolean[][] visit;
    public static void main(String[] args){
        Scanner scan = new Scanner(System.in);
        n = scan.nextInt();
        arr = new int[n][n];
        visit = new boolean[n][n];
        for(int i = 0; i < n; i++){
            for(int j = 0; j < n; j++)
                arr[i][j] = scan.nextInt();
        }
        dfs(0,0);
        System.out.println(min);

dx와 dy의 4방향 기저를 다음과 같이 설정합니다.

이후 arr는 2차원, visit도 2차원으로 전역 변수로 설정하고 min = 정수의 최대값으로 설정했습니다.

for(int i = 0; i < n; i++){
    for(int j = 0; j < n; j++)
        arr[i][j] = scan.nextInt();
}

arr는 Scan문으로 입력받았습니다.

n값이 딱히 크지 않고 코드의 가독성 때문에 저는 scan문을 선호하는 편입니다.

그리고 dfs(0,0)을 실행하는데, dfs문은 이렇게 생겼습니다.

static void dfs(int cnt, int sum){
    if(cnt == 3) {
        min = Math.min(min,sum);
        return;
    }

    for(int i = 1; i < n-1; i++){
        for(int j = 1; j < n-1; j++){
            if(!visit[i][j] && check(i,j)){
                visit[i][j] = true;
                dfs(cnt + 1, sum + search(i,j));
                visitClear(i,j);
                visit[i][j] = false;
            }
        }
    }
}

파라미터로 cnt와 sum을 int타입으로 가져옵니다.

cnt가 3이 될 때마다 return해줄 것이고 sum은 가격의 총합입니다. 

따라서

if(cnt == 3) {
    min = Math.min(min,sum);
    return;
}

cnt가 3이 될 때마다 min값과 sum값을 비교하여 작은값을 계속해서 min에 넣고 갱신한 후 return합니다.

for(int i = 1; i < n-1; i++){
    for(int j = 1; j < n-1; j++){
        if(!visit[i][j] && check(i,j)){
            visit[i][j] = true;
            dfs(cnt + 1, sum + search(i,j));
            visitClear(i,j);
            visit[i][j] = false;
        }
    }
}

cnt가 3이 아닐 때는 다음의 이중for문을 실행합니다.

그리고 i와 j값은 1부터 n-1까지 실행하는데 이유는 간단합니다.

꽃이 배열의 밖으로 나가는 것은 굳이 재배하지 않기 때문입니다.

만약 i가 0이거나 i가 n-1이면 꽃이 다 성장했을 때 배열 밖으로 튀어나가버리기 때문에 굳이 연산에 넣지않고 1부터 n-2까지의 인덱스만 탐색하도록 하겠습니다.

그럼 비교적 탐색량이 줄어들겠죠???

그리고 if문을 통해 visit이 false이고 check가 true인 인덱스만 탐색할 것인데요.

check함수는 

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

이렇게 생겼습니다.

기존의 visit하려는 index에서 상,하,좌,우의 모든 방향이 하나라도 true인 곳이 있다면 false를 return하고 방문한 적이 없다면 false를 return하여 check(i,j)에 반환합니다.

당연히 모두 방문하지 않았다면 (처음 실행된다면) visit은 false이고 check는 true가 됩니다.

이 다음 visit도 true로 바꾸어주고 dfs를 실행하는데 dfs에는 cnt+1을 담고 sum + search(i,j)하여 방문한 곳의 가격을 모두 더합니다.

search함수는 이렇게 생겼습니다.

static int search(int x, int y){
    int hap = arr[x][y];
    for(int i = 0; i < 4; i++){
        int nx = x + dx[i];
        int ny = y + dy[i];
        visit[nx][ny] = true;
        hap += arr[nx][ny];
    }
    return hap;
}

int 타입의 x와 y를 파라미터로 가져올 것이고 arr[x][y]는 hap에 담습니다.

그리고 4방향의 상,하,좌,우의 모든 인덱스에 대해 true로 바꾸고 hap에 arr의 새로 이동한 nx,ny들을 다 더한 후 hap을 return합니다.

당연히 방문하지 않았던 지점이기에 arr는 총 5번(중앙, 상,하,좌,우) 더해져서 return됩니다.

그렇게 모두 방문하다 보면 인덱스의 끝에 도착할텐데, 그럼 다시 visitClear함수를 실행해주어야 합니다.

static void visitClear(int x, int y){
    for(int i = 0; i < 4; i++){
        int nx = x + dx[i];
        int ny = y + dy[i];
        visit[nx][ny] = false;
    }
}

이 함수를 실행하는 이유는, 원래 백트래킹 함수는 방문했던 지점을 true로 바꾸고 dfs를 실행하고 visit을 다시 false로 바꿈으로 인해 모든 조합을 만들어 낼 수 있었지만 이번 꽃길 문제에서는 하나의 인덱스에 대해 총 5개의 인덱스가 파생되기 때문에 이 visit[i][j]뿐만이 아닌 나머지 4방향의 인덱스도 모두 false로 바꾸어주는 작업이 필요한 것입니다.

이 작용을 visitClear가 수행합니다.

4방향의 상,하,좌,우를 모두 false로 return하여 다음에 방문할 때도 무리 없이 check를 실행할 수 있게끔 만들어주어야 합니다.

마지막으로 visit도 false로 바꾸면 최종적으로 모든 3가지의 조합에 대해 겹치지 않는 인덱스에 한해서 조합을 완성할 수 있습니다.

 

감사합니다.