백준 14889 자바 - baegjun 14889 jaba

Question

[백준] 14889번 : 스타트와 링크 - JAVA [자바]

2020.07.15 16:57
JAVA - 백준 [BAEK JOON]/백트래킹

14889번: 스타트와 링크

예제 2의 경우에 (1, 3, 6), (2, 4, 5)로 팀을 나누면 되고, 예제 3의 경우에는 (1, 2, 4, 5), (3, 6, 7, 8)로 팀을 나누면 된다.

www.acmicpc.net

문제

저번 연산자 끼워넣기에 이어 이번 문제도 백준에서 제공하는 삼성 SW 역량 테스트 기출문제 중 하나다. 이 문제의 포인트는 두 팀으로 나누는데, 각 팀의 능력치 차이를 최소화 한다는 것이다. 한마디로 팀의 전력차가 적게 나도록 팀을 짜면 된다.

그렇게 어려운 문제는 아니니 천천히 풀어보자.

알고리즘 [접근 방법]

앞서 말했듯 두 팀으로 나누면 된다. 위 문제의 예시로 보자.

위와 같이 4명의 사람이 있을 때 두 팀으로 나눌 수 있는 방법, 즉 조합 방법은 다음과 같다.

[(1, 2), (3, 4)] , [(1, 3), (2, 4)], [(1, 4), (2, 3)]

그리고 각 팀의 능력치는 다음과 같다.

[5(S12 + S21), 7(S34 + S43)], [9(S13 + S31), 10(S24 + S42)], [6(S14 + S41), 6(S23 + S32)]

위 조합에서 각 팀의 점수차가 가장 적은 조합 방법은 1번과 4번이 한 팀, 2번과 3번이 한 팀인 방법이다. 각 팀의 점수는 6점으로 동일하여 점수차가 0으로 가장 적다.

이렇게 모든 조합의 경우의 수를 탐색하여 두 팀의 능력치가 최소가 되는 수를 찾고 이를 출력하면 된다.

그럼 코드로는 어떻게 구현해야 할까?

먼저 팀의 인원수인 N 을 입력을 받은 뒤, 위 표처럼 2차원 배열의 map 과 방문 여부를 표시할 visit 배열을 선언해준다. 즉, 다음과 같다.

int N = nextInt();	// 입력
int[][] map = new int[N][N];	// 조합 점수표
boolean[] visit = new boolean[N];	// 방문 여부

또한, 조합을 하기 위해 반복문과 반복문 안에 재귀호출을 하면 된다.

// idx는 인덱스, count는 조합 개수(=재귀 깊이)
static void combi(int idx, int count) {
	// 팀 조합이 완성될 경우
	if(count == N / 2) {
		/*
		 방문한 팀과 방문하지 않은 팀을 각각 나누어
		 각 팀의 점수를 구한 뒤 최솟값을 찾는다.
		*/
		return;
	}

	for(int i = idx; i < N; i++) {
		// 방문하지 않았다면?
		if(!visit[i]) {
			visit[i] = true;	// 방문으로 변경
			combi(i + 1, count + 1);	// 재귀 호출
			visit[i] = false;	// 재귀가 끝나면 비방문으로 변경
		}
	}
}

그 외로, 각 조합이 완성 되었을 때 점수를 구하는 것 또한 함수를 쓰면 더욱 편리하게 접근 할 수 있다. 이 부분은 따로 보여주진 않고 전체 코드에서 같이 보도록 하자.

2가지 방법을 사용하여 풀이한다.

다른 때와 마찬가지로 알고리즘은 위의 설명에서 했던 것을 쓸 것이고, 다만 입력 방법을 달리하여 각 성능의 차이를 보도록 할 것이다. 입력은 Scanner 와 BufferedReader 을 사용할 것이다.

1 . Scanner

2. BufferedReader

풀이

- 방법 1 : [Scanner]

import java.util.Scanner;

public class Main {
	
	static int N;
	static int[][] map;
	static boolean[] visit;
	
	static int Min = Integer.MAX_VALUE;
	
	public static void main(String[] args) {
    
		Scanner in = new Scanner(System.in);

		N = in.nextInt();

		map = new int[N][N];
		visit = new boolean[N];


		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				map[i][j] = in.nextInt();
			}
		}

		combi(0, 0);
		System.out.println(Min);

	}

	// idx는 인덱스, count는 조합 개수(=재귀 깊이)
	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++) {
				// i 번째 사람과 j 번째 사람이 true라면 스타트팀으로 점수 플러스 
				if (visit[i] == true && visit[j] == true) {
					team_start += map[i][j];
					team_start += map[j][i];
				}
				// i 번째 사람과 j 번째 사람이 false라면 링크팀으로 점수 플러스 
				else if (visit[i] == false && visit[j] == false) {
					team_link += map[i][j];
					team_link += map[j][i];
				}
			}
		}
		// 두 팀의 점수 차이 (절댓값)
		int val = Math.abs(team_start - team_link);
		
		/*
		 * 두 팀의 점수차가 0이라면 가장 낮은 최솟값이기 때문에
		 * 더이상의 탐색 필요없이 0을 출력하고 종료하면 된다.
		 */
		if (val == 0) {
			System.out.println(val);
			System.exit(0);
		}
		
		Min = Math.min(val, Min);
			
	}

}

가장 기본적인 방법이라 할 수 있겠다.

물론 이해를 돕기 위해 diff 함수에서 true 와 false 를 명시적으로 썼지만 위를 생략하고 써도 무방하다.

그리고 i 번째 사람과 j 번째 사람이 true라면, 즉 Sij 가 true 라면 스타트팀의 능력치(Sij 와 Sji)를 올려주면 된다.

- 방법 2 : [BufferedReader]

입력 방법을 Scanner 대신 BufferedReader 을 사용하여 풀이하는 방법이다. 단, BufferedReader 는 문자열을 한 줄로 읽기 때문에 각 능력치 점수별 공백을 기준으로 문자열을 분리해주어야하니 StringTokenizer 을 사용하여 풀도록 하겠다.

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);

	}

	// idx는 인덱스, count는 조합 개수(=재귀 깊이)
	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++) {
				// i 번째 사람과 j 번째 사람이 true라면 스타트팀으로 점수 플러스 
				if (visit[i] == true && visit[j] == true) {
					team_start += map[i][j];
					team_start += map[j][i];
				}
				// i 번째 사람과 j 번째 사람이 false라면 링크팀으로 점수 플러스 
				else if (visit[i] == false && visit[j] == false) {
					team_link += map[i][j];
					team_link += map[j][i];
				}
			}
		}
		// 두 팀의 점수 차이 (절댓값)
		int val = Math.abs(team_start - team_link);
		
		/*
		  두 팀의 점수차가 0이라면 가장 낮은 최솟값이기 때문에
		  더이상의 탐색 필요없이 0을 출력하고 종료하면 된다.
		 */
		if (val == 0) {
			System.out.println(val);
			System.exit(0);
		}
		
		Min = Math.min(val, Min);
				
	}

}

성능

채점 번호 : 20972088 - 방법 2 : BufferedReader

채점 번호 : 20972079 - 방법 1 : Scanner

입력의 경우는 확실히 Scanner 보다는 BufferedReader 가 빠른 걸 볼 수 있다.

정리

이렇게 백트래킹 카테고리의 마지막 문제가 끝났다. 문제를 풀어봤다면 알겠지만 대개 백트래킹 같은 탐색의 경우 DFS 방식을 사용하여 풀을 수 있다는 것을 알 수 있다. 특히 이 문제의 경우 조합 방법을 DFS를 사용하여 풀었는데, 이러한 조합 문제도 DFS를 통해 많이 풀이한다는 것을 알아두면 좋을 것이다.

혹여 이번 문제에서 이해되지 않거나 설명을 필요로 하는 부분이 있다면 댓글 남겨주시면 빠르게 답변드리도록 하겠다.