SWEA 1767. 프로세서 연결하기 (C++)

요약

상, 하, 좌, 우 탐색과 탐색을 안하고 지나가는 경우를 모두 고려해야한다.

---

문제

1개의 cell에는 1개의 Core 혹은 1개의 전선이 올 수 있다.
멕시노스의 가장 자리에는 전원이 흐르고 있다. Core와 전원을 연결하는 전선은 직선으로만 설치가 가능하며, 교차해서는 안된다.

멕시노스의 가장자리에 위치한 Core는 이미 전원이 연결된 것으로 간주한다.


[제약 사항]
1. 7 ≤  N ≤ 12
2. Core의 개수는 최소 1개 이상 12개 이하이다.
3. 최대한 많은 Core에 전원을 연결해도, 전원이 연결되지 않는 Core가 존재할 수 있다.


[입력]
각 테스트 케이스의 첫 줄에는 N값이 주어지며,
다음 N줄에 걸쳐서 멕시노스의 초기 상태가 N x N 배열로 주어진다.
0은 빈 cell을 의미하며, 1은 core를 의미하고,
그 외의 숫자는 주어지지 않는다.

[출력]
전선의 길이의 합을 출력한다.

---

풀이

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
using namespace std;

int map[15][15] = { 0, };
struct Node {
	int row, col;
};
vector<Node>v;
int lineCnt, coreCnt, N;
int minLines = 213456789;
int maxCores = -1;

void DFS(int a) {

	if (a == v.size()) {
		if (coreCnt > maxCores) {
			maxCores = coreCnt;
			minLines = lineCnt;
		}
		else if (coreCnt == maxCores) {
			if (lineCnt < minLines) minLines = lineCnt;
		}
		return;
	}

	Node now = v[a];
	int pr = now.row;
	int pc = now.col;
	bool abc = true;

	// 1. 위로 탐색 -> 가능하면 전선 입력
	for (int i = 0; i < pr; i++) {
		if (map[i][pc]) {
			abc = false;
			break;
		}
	}
	if (abc) {
		for (int i = 0; i < pr; i++) {
			map[i][pc] = 2;
			lineCnt++;
		}
		coreCnt++;
		DFS(a + 1);
		coreCnt--;
		for (int i = 0; i < pr; i++) {
			map[i][pc] = 0;
			lineCnt--;
		}
	}

	abc = true;
	// 2. 아래로 탐색
	for (int i = pr + 1; i < N; i++) {
		if (map[i][pc]) {
			abc = false;
			break;
		}
	}
	if (abc) {
		for (int i = pr + 1; i < N; i++) {
			map[i][pc] = 2;
			lineCnt++;
		}
		coreCnt++;
		DFS(a + 1);
		coreCnt--;
		for (int i = pr + 1; i < N; i++) {
			map[i][pc] = 0;
			lineCnt--;
		}
	}

	abc = true;
	// 3. 좌로 탐색
	for (int i = 0; i < pc; i++) {
		if (map[pr][i]) {
			abc = false;
			break;
		}
	}
	if (abc) {
		for (int i = 0; i < pc; i++) {
			map[pr][i] = 2;
			lineCnt++;
		}
		coreCnt++;
		DFS(a + 1);
		coreCnt--;
		for (int i = 0; i < pc; i++) {
			map[pr][i] = 0;
			lineCnt--;
		}
	}

	abc = true;
	// 4. 우로 탐색
	for (int i = pc + 1; i < N; i++) {
		if (map[pr][i]) {
			abc = false;
			break;
		}
	}
	if (abc) {
		for (int i = pc + 1; i < N; i++) {
			map[pr][i] = 2;
			lineCnt++;
		}
		coreCnt++;
		DFS(a + 1);
		coreCnt--;
		for (int i = pc + 1; i < N; i++) {
			map[pr][i] = 0;
			lineCnt--;
		}
	}

	abc = true;
	// 5. 탐색을 안하고 지나가는 경우
	DFS(a + 1);

}


int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie();
	cout.tie();

	int T;
	cin >> T;
	for (int tc = 1; tc <= T; tc++) {
		cin >> N;
		coreCnt = 0;
		lineCnt = 0;

		// 전역변수로 정의를 하면 값이 계속 받아져서 내려오니까 다시 main함수에서 정의해주자
		minLines = 213456789;
		maxCores = 0;

		v.clear();

		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				cin >> map[i][j];
				if (map[i][j])
				{
					// 가장자리에 있어서 이미 연결된 애들 제외하고 벡터에 푸시
					if (i == 0 || j == 0 || i == N - 1 || j == N - 1) coreCnt++;
					else v.push_back({ i,j });
				}
			}
		}

		// 벡터에 들어간 코어에 대해서 상하좌우 연결 확인
		DFS(0);

		cout << "#" << tc << " ";
		cout << minLines << "\n";
	}

	return 0;
}