[백준][JAVA알고리즘]14889번 풀이(스타트와 링크) - 초보도 이해하는 풀이

안녕하세요

인포돈 입니다.

백준 알고리즘 14889번 풀이입니다. 

* 참고사항
 - 개발환경은 eclipse을 기준으로 작성되었습니다.
 - java언어를 이용하여 문제를 풀이합니다.
 - 알고리즘 문제는 풀이를 보고 해답을 찾는 것도 중요하지만 무엇보다 스스로 풀이를 시도해봐야 합니다!!
(해당 풀이를 보기 전 충분히 문제에 대해 고민해봐야 합니다!)
 - 해당 풀이 말고도 수많은 풀이 방법이 존재합니다.

---

백준 14889 (스타트와 링크)

문제

오늘은 스타트 링크에 다니는 사람들이 모여서 축구를 해보려고 한다. 축구는 평일 오후에 하고 의무 참석도 아니다. 축구를 하기 위해 모인 사람은 총 N명이고 신기하게도 N은 짝수이다. 이제 N/2명으로 이루어진 스타트 팀과 링크 팀으로 사람들을 나눠야 한다.

 

BOJ를 운영하는 회사답게 사람에게 번호를 1부터 N까지로 배정했고, 아래와 같은 능력치를 조사했다. 능력치 Sij는 i번 사람과 j번 사람이 같은 팀에 속했을 때, 팀에 더해지는 능력치이다. 팀의 능력치는 팀에 속한 모든 쌍의 능력치 Sij의 합이다. Sij는 Sji와 다를 수도 있으며, i번 사람과 j번 사람이 같은 팀에 속했을 때, 팀에 더해지는 능력치는 Sij와 Sji이다.

 

N=4이고, S가 아래와 같은 경우를 살펴보자.

i / j	1	2	3	4
1		1	2	3
2	4		5	6
3	7	1		2
4	3	4	5

예를 들어, 1, 2번이 스타트 팀, 3, 4번이 링크 팀에 속한 경우에 두 팀의 능력치는 아래와 같다.

 

스타트 팀: S12 + S21 = 1 + 4 = 5

링크 팀: S34 + S43 = 2 + 5 = 7

1, 3번이 스타트 팀, 2, 4번이 링크 팀에 속하면, 두 팀의 능력치는 아래와 같다.

 

스타트 팀: S13 + S31 = 2 + 7 = 9

링크 팀: S24 + S42 = 6 + 4 = 10

축구를 재미있게 하기 위해서 스타트 팀의 능력치와 링크 팀의 능력치의 차이를 최소로 하려고 한다. 위의 예제와 같은 경우에는 1, 4번이 스타트 팀, 2, 3번 팀이 링크 팀에 속하면 스타트 팀의 능력치는 6, 링크 팀의 능력치는 6이 되어서 차이가 0이 되고 이 값이 최소이다.

 

입력

첫째 줄에 N(4 ≤ N ≤ 20, N은 짝수)이 주어진다. 둘째 줄부터 N개의 줄에 S가 주어진다. 각 줄은 N개의 수로 이루어져 있고, i번 줄의 j번째 수는 Sij이다 Sij이다. Sii는 항상 0이고, 나머지 Sij는 1보다 크거나 같고, 100보다 작거나 같은 정수이다.

 

출력

첫째 줄에 스타트 팀과 링크 팀의 능력치의 차이의 최솟값을 출력한다.

 

입력 예시

4
0 1 2 3
4 0 5 6
7 1 0 2
3 4 5 0

출력 예시

0

입력 예시

6
0 1 2 3 4 5
1 0 2 3 4 5
1 2 0 3 4 5
1 2 3 0 4 5
1 2 3 4 0 5
1 2 3 4 5 0

출력 예시

2

입력 예시

8
0 5 4 5 4 5 4 5
4 0 5 1 2 3 4 5
9 8 0 1 2 3 1 2
9 9 9 0 9 9 9 9
1 1 1 1 0 1 1 1
8 7 6 5 4 0 3 2
9 1 9 1 9 1 0 9
6 5 4 3 2 1 9 0

출력 예시

1

성공코드

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

public class Main {

	static int N;
	static int min = Integer.MAX_VALUE;
	static int[][] arr;
	static boolean[] visit;
	
	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		arr = new int[N][N];
		visit = new boolean[N];
		
		for(int i = 0 ; i < N ; i++) {
		StringTokenizer str = new StringTokenizer(br.readLine());
		for(int j = 0 ; str.hasMoreTokens();j++) {
			arr[i][j]= Integer.parseInt(str.nextToken());
		}
		}
		
		dfs(0,0);
		
		System.out.println(min);
		

}
	public static void dfs(int depth, int a) {
		
		if(depth == N/2) {
			diff();
			return;
		}
		
		for(int i = a ; i < N ; i++) {
			visit[i]=true;
			dfs(depth+1, i+1);
			visit[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(visit[i]==true && visit[j]==true) {
					start += arr[i][j];
					start += arr[j][i];
				}
				else if(visit[i]==false && visit[j]==false) {
					link += arr[i][j];
					link += arr[j][i];
				}
				
			}
		}
		
		int val = Math.abs(start - link);
		
		if(val == 0) {
			System.out.println(val);
			System.exit(0);
		}
		
		min=Math.min(min,val);
	}
	

}

네... 이번에도 역시나, 백 트레킹 문제는 어려웠습니다. 해당 문제에서 간단히 코드에 대한 핵심은 visit 배열입니다. visit배열을 이용하여 start와 link의 팀을 구변하는 거였습니다. 뭐 예를 들어 4명이 들어왔다고 하면, visit [4]를 만들어 각 인덱스에 true이면 start팀 false이면 link팀으로 구별하는 방식이다.

 

 사실 처음에 이러한 발상조차 하지 못하였다. 다른 정보를 찾아보면서 이해했던 방식이다. 사실 처음부터 이러한 방식을 생각하기 어려우니, 이번에 하나 배웠다고 생각하고 꼭 기억해보려 합니다.

 

 설명에 앞서서 문제에 대해 간략히 설명하자면, 짝수 사람을 반반 나누어준다. 나눈 사람들끼리의 시너지를 모두 더한 차이가 가장 작은 차이를 구하는 문제이다.

 

 STEP을 따라 하나하나 따져보면서 문제를 분석해 보도록 하죠.

---

알고리즘 흐름도

 입력받기 -> 팀 나누기 -> 나눈 팀 시너지 계산하기 -> 계산한 시너지가 이전에 나눈 팀보다 작은지 판별 -> 모든 경우의 수를 계산하여 최소 차이 구하기 -> 출력하기

---

STEP1 DFS 팀 나누기

public class Main {
	static boolean[] visit;
    ...
    public static void dfs(int depth, int a) {
		
		for(int i = a ; i < N ; i++) {
			visit[i]=true;
			dfs(depth+1, i+1);
			visit[i]=false;
		}	
	}
    ...
}

항상 DFS를 구현할 때는 IF문과 FOR문을 사용해야 합니다. 그중에 FOR문을 통해 팀을 나누어 주었습니다.

여기서 visit 변수는 각 팀을 결정하게 되는 거죠 true가 들어간 인덱스는 start팀, false가 들어간 인덱스는 link팀으로 판별하는 것입니다.

(여기서 for문에 i = a가 들어간 이유는, dfs를 통해 계속 재귀하면서, 그 이전 값들을 변경하면 안 되기 때문이죠)

 

물론 마지막에 visit [i] = false;를 넣어준 것은 당연히 dfs를 통해 4명을 뽑아내기 위해서이죠.

 

사실 이렇게만 보면 어떻게 4명이 되는 거야! 이렇게 생각하실 수 있습니다. 그럼 이제 바로 if문을 확인해보죠

public class Main {
	static boolean[] visit;
    ...
	public static void dfs(int depth, int a) {
		
		if(depth == N/2) {
			diff();
			return;
		}
		
		for(int i = a ; i < N ; i++) {
			visit[i]=true;
			dfs(depth+1, i+1);
			visit[i]=false;
		}	
	}
    ...
}

이때 diff는 무시해 주시고 보시죠 depth == N/2일 때 DFS가 멈추게 되죠. 즉 4명이 된다면, 해당 DFS를 멈추게 되죠. 이런 식으로 팀을 나누었다면 느낌이 오셨겠지만 diff함수를 통해 시너지의 합을 더해주면 끝

---

STEP2 diff() 각 팀의 시너지 합 구하기

	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(visit[i]==true && visit[j]==true) {
					start += arr[i][j];
					start += arr[j][i];
				}
				else if(visit[i]==false && visit[j]==false) {
					link += arr[i][j];
					link += arr[j][i];
				}
				
			}
		}
		
		int val = Math.abs(start - link);
		
		if(val == 0) {
			System.out.println(val);
			System.exit(0);
		}
		
		min=Math.min(min,val);
	}

스타트와 링크 알고리즘에서 2차원 배열을 통해서 값을 받았습니다. 그러면 그 행과 열에 맞는 값이 바로 두 선수의 시너지 점수가 되죠. 어떻게 구하는지는 간단합니다. 만약에 1 3 5 7이 start팀이 되고 2 4 6 8이 link팀이라고 생각해봅 시다. 그렇다면 visit에는 T F T F T F T F의 값이 들어가 있을 것입니다. 하나씩 비교하는 거죠 1 2 // 1 3 // 1 4  ~ // 1 8번까지 비교해가면서 만약 둘 다 TRUE라면 start팀에 있는 인원이겠죠. 그러면 각배 열의 행 열을 바꿔주어 모드 start변수에 넣어주면, 시너지 값들이 더해지죠. 이러한 방식으로 모두 시너지 값을 start와 link변수에 넣어주었다면,

 

이제 그 차이가 얼마인지 판단을 해야 합니다.

 

앞서 min = Integer.max_value로 선언해 주어습니다. 이에 따라 min과 val(차이) 비교하여 작은 것을 넣어주면 끝!

여기서 val==0이란 것은 가작 작은 수가 됩니다. 즉, 최솟값을 이미 찾았으므로 더 이상 프로그램을 실행할 이유가 없어짐으로 값을 출력해주고 프로그램을 종료해주면 됩니다.

---

사실 이번 스타트와 링크 알고리즘은 코드상으로 어려운 문제점은 없었지만, 팀을 visit변수로 나누어 생각한다는 점이 떠올리기 쉽지가 않았다. 앞으로 이런 식으로 2개의 팀 또는 2개로 나누어 따로 고려를 해야 하는 상황이 온다면 boolean변수를 잘 사용해야 된다고 생각합니다.