[백준] 14889 - 스타트와 링크 (Java)

[백준] 14889 - 스타트와 링크 (Java)

문제

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

풀이/후기

백트래킹 유형은 그동안 외면하다가 처음 풀어본 것 같다.

처음에는 그래프탐색이나 DP를 활용한 풀이를 생각했었다.

결국 DFS를 활용한 백트래킹으로 풀었다.

 

N명을 2개의 팀으로 나누기 위해 depth 변수를 활용한다.

depth+1을 계속해서 호출하며 N명의 절반이 될 때까지 재귀를 호출한다.

즉, 이렇게해서 팀을 나눈 것이다.

 

팀은 두개의 팀이기 때문에 true, false로 구분이 가능하다.

나는 true팀, false팀이라고 이해하니 편했다.

그리고 팀이 결성된 후에 각 팀의 점수를 비교하여 최소값을 구해주면 된다.

 

처음 생각할 때는 어려운데, 소스코드를 보면 또 엄청 어렵지 않다.

언제쯤 빠르게 아이디어를 떠올려 샤샤샥 풀 수 있을까!!?

코드

package Backtracking;

import java.io.*;
import java.util.*;

public class Problem14889 {

	static int N;
	static int[][] arr;
	static boolean[] visit;
	static int result = Integer.MAX_VALUE;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer str;
		N = Integer.parseInt(br.readLine());
		arr = new int[N + 1][N + 1];
		visit = new boolean[N + 1];

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

		back(1, 0);
		System.out.println(result);
	}

	static void back(int idx, int depth) {
		if (depth == N / 2) {
			diff();
			return;
		}

		for (int i = idx; i < N+1; i++) {
			if (!visit[i]) {
				visit[i] = true;
				back(i + 1, depth + 1);
				visit[i] = false;
			}
		}
	}

	static void diff() {
		int tS = 0;
		int tL = 0;

		for (int i = 1; i < N; i++) {
			for (int j = i; j < N + 1; j++) {
				if (visit[i] == true && visit[j] == true) {
					tS += arr[i][j] + arr[j][i];

				} else if (visit[i] == false && visit[j] == false) {
					tL += arr[i][j] + arr[j][i];
				}
			}
		}

		int val = Math.abs(tS - tL);
		result = Math.min(val, result);
	}
}

Commit

https://github.com/allrightDJ0108/CodingTestStudy/commit/60b70ce92d286b1406a2c435ab12059cd984b918

참고

https://velog.io/@kimmjieun/%EB%B0%B1%EC%A4%80-14889%EB%B2%88-%EC%8A%A4%ED%83%80%ED%8A%B8%EC%99%80-%EB%A7%81%ED%81%AC-Java-%EC%9E%90%EB%B0%94