백준 14889번 스타트와 링크 (DFS)

DFS를 이용하여 백준 문제를 풀어보자.

 

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

14889번: 스타트와 링크

 

---

기존에는 맵 형태의 탐색을 하기 위한 DFS방식만 알고 있었는데, DFS를 백트래킹을 이용하여 탐색하는 방식으로 구현할 수 있다는 것을 처음 알게 해 준 문제이다.

DFS, 백트래킹을 이용해서 팀을 나눠서 능력치의 합을 구하는 문제이다.

또는 순열을 이용해서 팀을 나눈 뒤, 능력치의 합을 구할 수도 있다. 

딱히 설명할 부분은 없으며 DFS와 백트래킹을 이용하는 방법(값을 호출하면서 따라 가보는 것을 추천)만 이해하면 된다.

 

 

<소스코드>

#include<iostream>

using namespace std;

int n;
int S[21][21];
int checked[21];
int ans = 0xfffffff;

void dfs(int idx, int cnt) {
	if (cnt == n / 2) {
		int start = 0, link = 0;

		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				if (checked[i] && checked[j])  start += S[i][j];
				if (!checked[i] && !checked[j]) link += S[i][j];
			}
		}

		int temp = abs(start - link);
		if (ans > temp) ans = temp;
		return;
	}

	for (int i = idx; i < n; i++) {
		checked[i] = true;
		dfs(i + 1, cnt + 1);
		checked[i] = false;
	}
}

int main(void) {
	cin >> n;

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> S[i][j];
		}
	}

	dfs(0, 0);

	cout << ans << '\n';
	return 0;
}

 

 

순열을 이용하는 방식을 알고싶은 분들은 아래 문제를 참조하면 도움이 될 것이다.

https://hungc.tistory.com/70

[Brute-Force] 15686번 치킨배달