소스 코드

/*
문제명  : swea_1767
메모리  : 13,704 kb
실행시간: 835 ms
결과    : Pass
*/
#include <iostream>
#include <vector>
#define endl "\n"
#define BLANK 0
#define CORE 1
#define LINE 2

using namespace std;

typedef pair<int, int> pos;

// 4방향 탐색을 위한 delta 상수
const int dy[] = { -1, +1, 0, 0 };
const int dx[] = { 0, 0, -1, +1 };

int n;						// 격자 한 변의 크기
int connectedCores;			// 현재까지 연결된 코어 수
int maxConnectedCores;		// 최대로 연결된 코어 수 
int lineLength;				// 현재까지 연결된 전선 길이
int minLineLength;			// 최소 전선 길이
vector<vector<int> > map;	// 셀 격자
vector<pos > candi;			// 가장자리 코어를 제외한 코어들

void input() {
	cin >> n;
	map.assign(n, vector<int>(n));

	// 테스트마다 candi 벡터 길이 0으로 초기화
	vector<pos >().swap(candi);

	for (int r = 0; r < n; ++r) {
		for (int c = 0; c < n; ++c) {
			cin >> map[r][c];

			// 가장자리에 존재하는 코어를 제외한 코어들 candi에 푸시
			if (map[r][c] == CORE && r != 0 && r != n - 1 && \
				c != 0 && c != n - 1) {
				candi.emplace_back(r, c);
			}
		}
	}

	candi.shrink_to_fit();

	// 다른 변수들 테스트마다 초기화
	connectedCores = 0;
	maxConnectedCores = -1;
	lineLength = 0;
	minLineLength = 0;
}

/*
	좌표 (y, x)가 격자를 벗어나기 전인지 여부를 반환
*/
int beforeEnd(int y, int x) {
	return !(y < 0 || y >= n || x < 0 || x >= n);
}

/*
	최대 연결 코어 수보다 현재까지 연결된 코어 수가 더 클 경우
	최대 연결 코어 및 최소 전선 길이 업데이트
*/
void update() {
	if (connectedCores > maxConnectedCores) {
		minLineLength = lineLength;
		maxConnectedCores = connectedCores;
	}
	else if (connectedCores == maxConnectedCores) {
		if (minLineLength > lineLength) {
			minLineLength = lineLength;
		}
	}
}

/*
	주어진 core 기준 dir 방향으로 탐색 시
	다른 전선 및 코어가 존재하지 않으면
	전선 깔기, 현재 전선 길이 증가, 현재까지 연결된 코어 수 증가.
*/
void check(const pos& core, int dir) {
	int y = core.first + dy[dir];
	int x = core.second + dx[dir];

	bool isConnected = true;
	int tmpLineNum = 0;
	vector<vector<int> > copy;
	copy = map;
	while (isConnected && beforeEnd(y, x)) {
		if (map[y][x] == BLANK) {
			map[y][x] = LINE;
			++tmpLineNum;

			y += dy[dir];
			x += dx[dir];
		}
		else {
			isConnected = false;
		}
	}

	if (isConnected) {
		++connectedCores;
		lineLength += tmpLineNum;
	}
	else {
		// 코어를 전원에 연결할 수 없으므로 이때까지 깔았던 전선 초기화
		map = copy;
	}
}

/*
	count에 해당하는 인덱스의 코어에 대해 4방향 + 제자리 탐색 수행.
	만약, (현재까지 연결된 코어 수 + 앞으로 탐색이 남은 코어 수)가
	최대 연결 코어 수보다 작을 경우 더 이상의 탐색이 의미없으므로 반환.
*/
void findMin(int count) {
	if (count == candi.size()) {
		update();
		return;
	}

	// 최대로 연결된 코어 수보다 남은 코어 수 + 현재까지 연결된 
	// 수가 작을 경우 탐색 중지
	if (maxConnectedCores > connectedCores + \
		(int)candi.size() - count) {
		return;
	}

	vector<vector<int> > copyMap;
	copyMap = map;
	int copyConnectedCores = connectedCores;
	int copyLineNum = lineLength;

	for (int dir = 0; dir < 5; ++dir) {
		if (dir == 4) {
			findMin(count + 1);
		}
		else {
			check(candi[count], dir);

			findMin(count + 1);

			lineLength = copyLineNum;
			connectedCores = copyConnectedCores;
			map = copyMap;
		}
	}
}

void solve() {
	input();

	findMin(0);

	cout << minLineLength << endl;
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	freopen("sample_input.txt", "r", stdin);

	int TC;
	cin >> TC;
	for (int tc = 1; tc <= TC; ++tc) {
		cout << "#" << tc << " ";
		solve();
	}

	return 0;
}

해설

격자에서 4방향 탐색 + 제자리 탐색 하는 백트래킹 문제.
단, 시간초과 방지를 위해 불필요한 탐색 커팅 기법 사용 필수.