(*풀이진행중)백트랙킹 - 14889번

3월 2일(목) - 백트랙킹(14889번)

14889번: 스타트와 링크

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

 

최초 생각 정리

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

 

문제점

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

 

풀이

(3월 2일까지의 풀이 -> 틀림)

#define _CRT_SECURE_NO_WARNINGS
#pragma warning(disable: 4996)
#define GAP(x, y) (x) > (y) ? (x - y) : (y - x)

#include <stdio.h>
#include <limits.h>
int N;
int table[20][20];
int visited[20] = { 0, };
int min = INT_MAX;

void DFS(int cur, int x)
{
	if (x == N / 2)
	{
		int start = 0;
		int link = 0;
		int balance = 0;

		for (int i = 0; i < N ; i++)
		{
			for (int j = 0; j < N; j++)
			{
				if (visited[i] == 1 && visited[j] == 1)
				{
					start = start + table[i][j];
				}
				else if (visited[i] == 0 && visited[j] == 0)
				{
					link = link + table[j][i];
				}
			}
		}

		balance = GAP(start, link);
		if (min > balance)
		{
			min = balance;
		}
		return;
	}

	for (int i = cur + 1; i < N; i++)
	{
		visited[i] = 1;
		DFS(i, x + 1);
		visited[i] = 0;
	}
	return;
}

int main(void)
{
	scanf("%d", &N);

	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < N; j++)
		{
			scanf("%d", &table[i][j]);
		}
	}

	for (int i = 0; i < N; i++)
	{
		visited[i] = 1;
		DFS(0, 1);
		visited[i] = 0;
	}

	printf("%d", min);
	return 0;
}

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ