[C++] 삼성 1767. [SW Test 샘플문제] 프로세서 연결하기

#include<iostream>
#include<vector>

using namespace std;

int N;
int cell[12][12];
int maxCore;
int minDist;
vector<pair<int, int>> core;

bool checkLine(int x, int y, int dir) {
	if (dir == 0) {
		for (int j = y + 1; j < N; j++) {
			if (cell[x][j] != 0) return false;
		}
	}
	else if (dir == 1) {
		for (int i = x + 1; i < N; i++) {
			if (cell[i][y] != 0) return false;
		}
	}
	else if (dir == 2) {
		for (int j = y - 1; j >= 0; j--) {
			if (cell[x][j] != 0) return false;
		}
	}
	else if (dir == 3) {
		for (int i = x - 1; i >= 0; i--) {
			if (cell[i][y] != 0) return false;
		}
	}

	return true;
}

int drawLine(int x, int y, int dir) {
	int count = 0;
	if (dir == 0) {
		for (int j = y + 1; j < N; j++) {
			cell[x][j] = 2;
			count++;
		}
	}
	else if (dir == 1) {
		for (int i = x + 1; i < N; i++) {
			cell[i][y] = 2;
			count++;
		}
	}
	else if (dir == 2) {
		for (int j = y - 1; j >= 0; j--) {
			cell[x][j] = 2;
			count++;
		}
	}
	else if (dir == 3) {
		for (int i = x - 1; i >= 0; i--) {
			cell[i][y] = 2;
			count++;
		}
	}

	return count;
}

void eraseLine(int x, int y, int dir) {
	if (dir == 0) {
		for (int j = y + 1; j < N; j++) {
			cell[x][j] = 0;
		}
	}
	else if (dir == 1) {
		for (int i = x + 1; i < N; i++) {
			cell[i][y] = 0;
		}
	}
	else if (dir == 2) {
		for (int j = y - 1; j >= 0; j--) {
			cell[x][j] = 0;
		}
	}
	else if (dir == 3) {
		for (int i = x - 1; i >= 0; i--) {
			cell[i][y] = 0;
		}
	}
}

void dfs(int idx, int coreCount, int dist) {
	if (idx == core.size()) {
		if (maxCore < coreCount) {
			maxCore = coreCount;
			minDist = dist;
		}
		else if (maxCore == coreCount) {
			if (minDist > dist)
				minDist = dist;
		}
		return;
	}

	for (int dir = 0; dir < 4; dir++) {
		if (checkLine(core[idx].first, core[idx].second, dir)) {
			dfs(idx + 1, coreCount + 1, dist + drawLine(core[idx].first, core[idx].second, dir));
			eraseLine(core[idx].first, core[idx].second, dir);
		}
	}
	dfs(idx + 1, coreCount, dist);
}

int main() {
	int T;
	cin >> T;
	for (int t = 1; t <= T; t++) {
		cin >> N;
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				cin >> cell[i][j];
				if (cell[i][j] == 1 && i != 0 && j != 0 && i != N - 1 && j != N - 1)
					core.push_back(make_pair(i, j));
			}
		}

		maxCore = 0;
		minDist = 999999;
		dfs(0, 0, 0);

		cout << "#" << t << " " << minDist << endl;
		core.clear();
	}

	return 0;
}