[백준 14889] 스타트와 링크 / 자바 /dfs

#문제         

레벨: S1
알고리즘: dfs 
풀이시간: 1시간
힌트 참조 유무:

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

 

---

 

#문제 풀이        

dfs로 조합을 구한 후 조합이 완성될 때마다 답의 최솟값을 구하면 되는 쉬운 문제이다. 설명은 생략하겠다.

---

#배운 점    

dfs함수는 사람마다 구현하는 게 다 다르다. 

 visited[] = true 순서이다. 

재귀호출 전 true만들기

    dfs(int i) {
        for (int j = i; j < N; j++) {
            if(visited[j])
                continue;
            visited[] =true;
            dfs(j);
        }
    }

 

재귀호출 후 첫 코드에서 true만들기

    dfs(int i) {
        visited[] =true;
        for (int j = i; j < N; j++) {
            if(visited[j])
                continue;
            dfs(j);
        }
    }

 

이것도 사고의 흐름이 편한대로 작성하면 될 것이다. 

자기만의 dfs 함수 짜는 법이 익숙해지는 것이 중요한 것 같다.

---

#풀이 코드      

 

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

public class Main {
    static int N;
    static int[][] map;
    static boolean[] visit;
    static int Min = Integer.MAX_VALUE;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        map = new int[N][N];
        visit = new boolean[N];
        
        for (int i = 0; i < N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine(), " ");
            for (int j = 0; j < N; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        
        combi(0, 0);
        System.out.println(Min);
    }

    static void combi(int idx, int count) {
        if(count == N/2) {
            diff();
            return;
        }
        
        for(int i = idx; i < N; i++) {
            if(!visit[i]) {
                visit[i] = true;
                combi(i + 1, count + 1);
                visit[i] = false;
            }
        }
    }

    static void diff() {
        int team_start = 0;
        int team_link = 0;
        
        for (int i = 0; i < N - 1; i++) {
            for (int j = i + 1; j < N; j++) {
                if (visit[i] && visit[j]) {
                    team_start += map[i][j] + map[j][i];
                } else if (!visit[i] && !visit[j]) {
                    team_link += map[i][j] + map[j][i];
                }
            }
        }
        
        int diff = Math.abs(team_start - team_link);
        Min = Math.min(diff, Min);
    }
}

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

public class Main {
    static int N;
    static int[][] ability;
    static boolean[] isStartTeam;
    static int minDifference = Integer.MAX_VALUE;

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

        for (int i = 0; i < N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine(), " ");
            for (int j = 0; j < N; j++) {
                ability[i][j] = Integer.parseInt(st.nextToken());
            }
        }

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

    static void dfs(int index, int count) {
        if (index == N || count == N / 2) {
            if (count == N / 2) {
                calculateDifference();
            }
            return;
        }

        // 현재 선수를 스타트 팀에 넣는 경우
        isStartTeam[index] = true;
        dfs(index + 1, count + 1);

        // 현재 선수를 스타트 팀에 넣지 않는 경우 (링크 팀에 넣는 경우)
        isStartTeam[index] = false;
        dfs(index + 1, count);
    }

    static void calculateDifference() {
        int startTeamAbility = 0;
        int linkTeamAbility = 0;

        for (int i = 0; i < N; i++) {
            for (int j = i + 1; j < N; j++) {
                if (isStartTeam[i] && isStartTeam[j]) {
                    startTeamAbility += ability[i][j] + ability[j][i];
                } else if (!isStartTeam[i] && !isStartTeam[j]) {
                    linkTeamAbility += ability[i][j] + ability[j][i];
                }
            }
        }

        int difference = Math.abs(startTeamAbility - linkTeamAbility);
        minDifference = Math.min(minDifference, difference);
    }
}

---