[BOJ - JAVA] 21278 - 호석이 두 마리 치킨 (브루트포스)

# 주소

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

21278번: 호석이 두 마리 치킨

# 문제

# 문제 해설 및 코드 리뷰

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    static int n, m;
    static int[][] arr;
    static int[] place = new int[2];
    static int[] minPlace = new int[2];
    static boolean[] visit;
    static int min = Integer.MAX_VALUE;
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        n = scan.nextInt();
        m = scan.nextInt();
        visit = new boolean[n+1];
        arr = new int[n + 1][n + 1];
        for(int i = 0; i <= n; i++){
            for(int j = 0; j <= n; j++){
                if(i == j)
                    continue;
                arr[i][j] = n;
            }
        }
        for (int i = 0; i < m; i++) {
            int x = scan.nextInt();
            int y = scan.nextInt();
            arr[x][y] = arr[y][x] = 1;
        }
        check();
        dfs(1,0);
        System.out.println(minPlace[0] + " " + minPlace[1] + " " + min);
    }
    static void check(){
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= n; j++){
                for(int k = 1; k <= n; k++){
                    arr[j][k] = Math.min(arr[j][k], arr[j][i] + arr[i][k]);
                }
            }
        }
    }
    static void dfs(int start, int cnt){
        if(cnt == 2){
            int sum = 0;
            for(int i = 1; i <= n; i++){
                if(!visit[i]){
                    int mmin = Integer.MAX_VALUE;
                    for(int j = 0; j < 2; j++){
                        mmin = Math.min(arr[i][place[j]], mmin);
                    }
                    sum += mmin * 2;
                }
            }
            if(min > sum){
                for(int i = 0; i < 2; i++){
                    minPlace[i] = place[i];
                }
                min = sum;
            }
            return;
        }
        for(int i = start; i <= n; i++){
            if(!visit[i]){
                visit[i] = true;
                place[cnt] = i;
                dfs(i, cnt+1);
                visit[i] = false;
            }
        }
    }
}

플로이드 와샬 알고리즘을 처음 접했습니다.

인덱스를 백트래킹으로 찾아서 최소값을 구하는 과정이 자꾸 삑사리가 나서 Queue에도 담아보고 arr애도 담아보았지만 마땅한 방법을 못찾아서 다른 분들의 코드를 참고했습니다.

결론적으로 플로이드-와샬 알고리즘을 알고 있어야 굉장히 수월하게 풀릴 수 있더군요.

그럼 플로이드-와샬 알고리즘이 무엇일까요?

-> 모든 정점에서 모든 정점으로의 최단거리를 구하는데 알고리즘으로 기본적으로 '거쳐가는 정점'을 기준으로 알고리즘을 수행합니다. 거쳐가는 노드를 중심으로 반복문을 진행하기 때문에 거쳐가는 노드를 하나씩 다 설정해서 확인합니다.

또 한 모든 정점에서 모든 정점으로 가는 최단경로를 구하는 것이기 때문에 2차원 배열을 사용합니다.

static void floyd(){
        for(int k = 0 ; k<N; k++){
            for(int i = 0; i<N ;i++){
                for(int j = 0 ; j<N ;j++){
                    if(map[i][j] > map[i][k] + map[k][j]){
                        map[i][j] = map[i][k] + map[k][j];
                    }
                }
            }
        }
    }

그렇기 때문에 코드를 3중 for문으로 작성해야하며 계속해서 최소값을 갱신해줄 필요가 있습니다.

이 문제도 마찬가지입니다. 코드를 보면서 살펴봅시다.

public static void main(String[] args) {
    Scanner scan = new Scanner(System.in);
    n = scan.nextInt();
    m = scan.nextInt();
    visit = new boolean[n+1];
    arr = new int[n + 1][n + 1];
    for(int i = 0; i <= n; i++){
        for(int j = 0; j <= n; j++){
            if(i == j)
                continue;
            arr[i][j] = n;
        }
    }

n과 m을 static에 선언했기 떄문에 scan으로 입력받고 visit과 arr의 크기는 n+1로 선언합니다.

그리고 2중 for문으로 arr값을 n으로 초기화하는데 단 i와 j가 같은 인덱스일 경우 탐색하지 않습니다.

for (int i = 0; i < m; i++) {
    int x = scan.nextInt();
    int y = scan.nextInt();
    arr[x][y] = arr[y][x] = 1;
}

입력되는 모든 x행y열의 값과 y행x열의 값을 1로 초기화합니다.

이 지점들이 연결된 간선간의 길이입니다.

그리고 각 점마다의 노드간 거리를 구해야하는데 이 때 플로이드 와샬 알고리즘을 사용합니다.

check();
    dfs(1,0);
    System.out.println(minPlace[0] + " " + minPlace[1] + " " + min);
}

저는 check()함수로 표현했습니다.

static void check(){
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            for(int k = 1; k <= n; k++){
                arr[j][k] = Math.min(arr[j][k], arr[j][i] + arr[i][k]);
            }
        }
    }
}

지금 보시면, 3중for문으로 표현한 것을 알 수 있습니다.

i,j,k를 사용하여 arr[j][k]는 자기 자신의 값과 돌아서 가는 arr[j][i] + arr[i][k]의 값 중 더 작은 값을 채택하여 arr[j][k]에 갱신합니다.

이 과정이 이루어지면 모든 값들 간의 거리가 2차원 배열에 담기게 됩니다.

그리고 dfs에 (1,0)을 넣고 실행하겠습니다.

static void dfs(int start, int cnt){

dfs의 파라미터로는 start와 cnt를 받아오도록 했습니다.

start는 다음 dfs문을 실행할 때의 현재 Index이고 cnt는 현재 탐색한 횟수를 의미합니다.

치킨집은 총 2군데 탐색해야 하기 때문에 당연히 cnt == 2가 될 때마다 따로 로직을 만들어서 return해줍니다.

그리고 cnt != 2일 때에는 for문을 실행하여 백트래킹을 실행하겠습니다.

for(int i = start; i <= n; i++){
    if(!visit[i]){
        visit[i] = true;
        place[cnt] = i;
        dfs(i, cnt+1);
        visit[i] = false;
    }
}

로직은 다음과 같습니다.

if(!visit[i])일 때 visit은 true, place[cnt] = i로 넣고 dfs(i, cnt + 1)을 실행합니다.

place[cnt] = i 는 인덱스를 의미합니다. cnt의 값은 0, 1중 왔다갔다 하기 때문에 치킨집을 선정할 인덱스를 의미합니다.

만약 3,5지점을 치킨집으로 하고 싶으면 place[0] = 3, place[1] = 5가 되겠지요.

또한 dfs재귀함수를 이용하여 (i, cnt + 1)를 실행하였는데, 이는 현재의 인덱스를 파라미터로 담고 cnt를 증가시키겠단 뜻입니다.

만약 cnt가 2가 된다면 위에서 언급했듯 따로 로직을 처리해주어야만 하겠습니다.

마지막으로 visit[i] = false를 붙히면 모든 조합의 경우의 수를 완성할 수 있게됩니다.

그럼 cnt == 2일 때 로직을 보겠습니다.

if(cnt == 2){
    int sum = 0;
    for(int i = 1; i <= n; i++){
        if(!visit[i]){
            int mmin = Integer.MAX_VALUE;
            for(int j = 0; j < 2; j++){
                mmin = Math.min(arr[i][place[j]], mmin);
            }
            sum += mmin * 2;
        }
    }
    if(min > sum){
        for(int i = 0; i < 2; i++){
            minPlace[i] = place[i];
        }
        min = sum;
    }
    return;
}

만약 cnt == 2라면 sum = 0으로 선언하겠습니다.

그리고 for문을 이용하여 visit[i] 가 false인 인덱스는 노드 간의 거리를 담아둘 것입니다.

이 때 mmin과 min은 다른데, mmin을 Integer.MAX_VALUE라고 초기화하면 반례가 생기지 않으므로 이렇게 지정했습니다.

또한 그 다음 for문에서 mmin = Math.min (arr[i][place[j]], mmin); 이라고 작성한 이유는

mmin의 값은 어짜피 INF이기 때문에 그것보다 적은 arr[i][place[j]]라면 갱신하라는 의미입니다.

place[j]는 위에서 살펴봤듯, 치킨집의 위치입니다.

arr[i][place[j]]는 i와 j간의 거리를 의미하는 값이 세겨지겠지요.

그래서 visit도 false일 때 탐색이 되는 것입니다.

만약 visit이 true인 곳은 왜 탐색안하나요? 라고 물으신다면.. visit이 true여도 탐색은 가능하게 로직을 짤 수 있습니다만 visit이 false인 곳을 기준으로 탐색하는 것이 낫다고 생각이 들어서 그렇습니다. 허..

 

어쨌든 갖고온 mmin을 sum에 2배 곱하여 더합니다.

그런데 이렇게 다 구한 sum보다 더 적은 sum이 있다면 minPlace라는 곳에 place의 값들을 저장하고 min = sum으로 바꾸어줍니다.

그렇게 계속 return하여 모든 조합의 경우의 수에 대해 탐색을 완료하고 출력할 대에 minPlace와 min을 출력하면 정답이 되겠습니다.

감사합니다.