14889. 스타트와 링크

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

14889번: 스타트와 링크

<JAVA>

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.List;
import java.util.StringTokenizer;

class Main {
	static int N;
	static boolean visit[] = new boolean[20];
	static int map[][] = new int[20][20];
	static int _min = 2147483647;;

	static void DFS(int cur, int cnt) {
		if (cnt == N / 2) {
			List<Integer> start = new LinkedList<>();
			List<Integer> link = new LinkedList<>();
			for (int i = 0; i < N; ++i) {
				if (visit[i]) {
					start.add(i);
				} else {
					link.add(i);
				}
			}
			int start_sum = 0, link_sum = 0;
			for (int i = 0; i < start.size(); ++i) {
				for (int j = i + 1; j < start.size(); ++j) {
					int start_x = start.get(i);
					int start_y = start.get(j);
					int link_x = link.get(i);
					int link_y = link.get(j);
					start_sum += map[start_x][start_y] + map[start_y][start_x];
					link_sum += map[link_x][link_y] + map[link_y][link_x];
				}
			}
			_min = Math.min(_min, Math.abs(start_sum - link_sum));
			return;
		}
		for (int i = cur + 1; i < N; ++i) {
			if (visit[i] == false) {
				visit[i] = true;
				DFS(i, cnt + 1);
				visit[i] = false;
			}
		}
	}

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

<C++>

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int N;
bool visit[20];
int map[20][20];
int _min = 2147483647;
void DFS(int cur, int cnt)
{
	if (cnt == N / 2)
	{
		vector<int> start, link;
		for (int i = 0; i < N; ++i)
		{
			if (visit[i])
			{
				start.push_back(i);
			}
			else {
				link.push_back(i);
			}
		}
		int start_sum = 0, link_sum = 0;
		for (int i = 0; i < start.size(); ++i)
		{
			for (int j = i + 1; j < start.size(); ++j)
			{
				int start_x = start[i];
				int start_y = start[j];
				int link_x = link[i];
				int link_y = link[j];
				start_sum += map[start_x][start_y] + map[start_y][start_x];
				link_sum += map[link_x][link_y] + map[link_y][link_x];
			}
		}
		_min = min(_min, abs(start_sum - link_sum));
		return;
	}
	for (int i = cur + 1; i < N; ++i)
	{
		if (visit[i] == false)
		{
			visit[i] = true;
			DFS(i, cnt + 1);
			visit[i] = false;
		}
	}
}
int main()
{
	ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	cin >> N;
	for (int i = 0; i < N; ++i)
	{
		for (int j = 0; j < N; ++j)
		{
			cin >> map[i][j];
		}
	}
	DFS(0, 0);
	cout << _min << "\n";
	return 0;
}