[백준] Silver 1. 스타트와 링크

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

 

사용 알고리즘

• 백트래킹
• 브루트 포스

풀이

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


public class Main {
    static int n;
    static int [][] board;
    static boolean [] visited;
    static int min = Integer.MAX_VALUE;
    // 재귀 종료 조건 -> depth가 n/2도달
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());

        board = new int[n][n];
        visited = new boolean[n];
        for(int i = 0; i < n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for(int j = 0; j < n; j++){
                board[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        dfs(0, 0);
        System.out.println(min);
    }

    public static void dfs(int idx, int depth) {
        if (depth == n/2) {
            diff();

            return;
        }

        for(int i = idx; i < n; i++){
            if (!visited[i]) {
                visited[i] = true;
                dfs(i + 1, depth + 1);
                visited[i] = false;
            }
        }
    }

    public static void diff() {
        int start = 0;
        int link = 0;
        for(int i = 0; i < n - 1; i++){
            for(int j = i + 1; j < n; j++){
                if (visited[i] && visited[j]) {
                    start += board[i][j];
                    start += board[j][i];
                }

                else if (!visited[i] && !visited[j]) {
                    link += board[i][j];
                    link += board[j][i];
                }
            }
        }
        int res = Math.abs(start - link);
        min = Math.min(min, res);
    }
}

 

회고

... 이전에 풀었던 문제지만 또 답안을 참고했다.

 

문제를 다시 풀면서 두개의 근본적인 문제를 발견했다.

 

1. visited 배열은 1차원으로 표현 가능하다.

모든 배열에 대해서 방문 체크를 한다고 생각해서 2차원으로 선언했지만, 1차원으로 더욱 쉽게 할 수 있었다. 

N = 4일때를 가정해보자. 스타트 팀의 가짓수는 (1,2), (1,3), (1,4), (2,3), (2.4), (3,4) 이렇게 6가지가 된다. (링크 팀도 동일할 것이다)

 

1차원 배열로 만들어서 방문 처리를 해주면

true true false false 
true false true false 
true false false true 
false true true false 
false true false true 
false false true true

 

보이는가? (1,2), (1,3), (1,4), (2,3), (2.4), (3,4) 결과가 정확히 나오는 것을 볼 수 있다. 

 

2. 아직도 헷갈리는 재귀 시작점 설정....

for(int i = idx; i < n; i++){
    if (!visited[i]) {
        visited[i] = true;
        dfs(i + 1, depth + 1);
        visited[i] = false;
    }
}

 

여기서 dfs(idx + 1, depth + 1)이 아닌 이유는?

true true false false 
true false true false 
true false false true 
false true true false 
false true false true 
false true true false -> 중복
false false true true 
false true false true -> 중복
false false true true -> 중복

(1,2), (1,3), (1,4), (2,3), (2,4), (2,3), (3,4), (2,4), (3,4)와 같이 중복이 발생한다.

 

// idx + 1일때
idx: 0 
idx: 1
idx: 1
idx: 1
idx: 0
idx: 1
idx: 1
idx: 0
idx: 1
idx: 1
idx: 0
idx: 1
idx: 1

// i + 1일떄
idx: 0
idx: 1
idx: 1
idx: 1
idx: 0
idx: 2
idx: 2
idx: 0
idx: 3
idx: 0

 

i+1은 이전에 탐색한 다음 부분부터 탐색을 진행하기 때문에 중복이 존재하지 않는다.

 

1차원일 때 visited처리와 (이전 N-Queen도 마찬가지) 재귀의 시작점에 대해서 계속 숙달하자..