1461. 프로세서 연결하기

Code Battle (`23 동계 대학생 S/W 알고리즘 특강 기초학습 문제)

본 게시글은 개인 학습 용도로 작성한 게시글입니다.
(문제 출처: SW Expert Academy)

프로세서 연결하기

Code Battle (`23 동계 대학생 S/W 알고리즘 특강 기초학습 문제)

본 게시글은 개인 학습 용도로 작성한 게시글입니다.
(문제 출처: https://swexpertacademy.com)

분할 정복으로 풀이
코어의 위치를 스택에 push 해두고, 하나씩 pop해가며 전선을 배치하는 경우의 수를 검사한다.
$N$개의 코어가 있을 때, 각 코어는 4방위로 전선을 설치하거나 아예 설치하지 않을 수도 있다. 즉, 조합 가능한 경우의 수는 $5^{N}$가지가 있다.
$N$은 최대 $12$이므로, 완전탐색으로 풀이를 시도해도 아슬아슬하게 통과가 가능할 것 같다 생각했다.
solve_sub_problem()에서는 실행시간 최적화를 위해 다음과 같은 논리를 적용하였다:
- n_cores_placed개의 코어(의 전선)이 설치 되었을 때, 앞으로 설치 가능한 코어의 수 n_cores_left를 모두 설치하더라고 지금까지 설치된 최대 개수 answer_max_n_cores_placed 보다 적다면, 해당 경우의 수는 더 이상 검사하지 않는다.
- 가장자리에 있는 코어는 이미 전원이 연결되어있다고 볼 수 있으므로 검사에서 제외한다.

#include <iostream>
#define MAX_N 12
#define MAX_CORE 12

#define CELL_EMPTY '0'
#define CELL_CORE '1'
#define CELL_LINE 'x'

#define DIRECTION_TOP 0
#define DIRECTION_BOTTOM 1
#define DIRECTION_LEFT 2
#define DIRECTION_RIGHT 3

using namespace std;

char board[MAX_N+1][MAX_N+1];
int board_size;

int cores_y[MAX_CORE];
int cores_x[MAX_CORE];
int n_cores;

int answer_min_line_length;
int answer_max_n_cores_placed;

int next_x(int x, int direction) {
	if (direction == DIRECTION_LEFT) {
		x--;
	}
	else if (direction == DIRECTION_RIGHT) {
		x++;
	}
	return x;
}

int next_y(int y, int direction) {
	if (direction == DIRECTION_TOP) {
		y--;
	}
	else if (direction == DIRECTION_BOTTOM) {
		y++;
	}
	return y;
}

bool is_occupied(int y, int x) {
	return board[y][x] != CELL_EMPTY;
}

bool is_on_board(int y, int x) {
	return x >= 0 && y >= 0 && x < board_size && y < board_size;
}

bool is_on_edge(int y, int x) {
	return x == 0 || y == 0 || x == board_size-1 || y == board_size-1;
}

bool is_line_installable(int y, int x, int direction) {
	while (true) {
		x = next_x(x, direction);
		y = next_y(y, direction);
		if (!is_on_board(y, x)) {
			break;
		}
		if (is_occupied(y, x)) {
			return false;
		}
	}
	return true;
}

int install_line(int y, int x, int direction) {
	int line_length = 0;
	while (true) {
		x = next_x(x, direction);
		y = next_y(y, direction);
		if (!is_on_board(y, x)) {
			break;
		}
		board[y][x] = CELL_LINE;
		line_length++;
	}
	return line_length;
}

void uninstall_line(int y, int x, int direction) {
	while (true) {
		x = next_x(x, direction);
		y = next_y(y, direction);
		if (!is_on_board(y, x)) {
			break;
		}
		board[y][x] = CELL_EMPTY;
	}
}

void solve_sub_problem(int nth_cores_left, int n_cores_placed, int line_length) {
	if (nth_cores_left+n_cores_placed < answer_max_n_cores_placed) {
		return;
	}
	if (nth_cores_left == 0) {
		if (n_cores_placed > answer_max_n_cores_placed) {
			answer_max_n_cores_placed = n_cores_placed;
			answer_min_line_length = line_length;
		}
		else if (n_cores_placed == answer_max_n_cores_placed && line_length < answer_min_line_length) {
			answer_min_line_length = line_length;
		}
		return;
	}
	int y = cores_y[nth_cores_left-1];
	int x = cores_x[nth_cores_left-1];
	solve_sub_problem(nth_cores_left-1, n_cores_placed, line_length);
	for (int direction = DIRECTION_TOP; direction <= DIRECTION_RIGHT; direction++) {
		if (is_line_installable(y, x, direction)) {
			solve_sub_problem(nth_cores_left-1, n_cores_placed+1, line_length + install_line(y, x, direction));
			uninstall_line(y, x, direction);
		}
	}
}

static void solve(int test_case_no)
{
	int y, x;
	n_cores = 0;
	answer_max_n_cores_placed = 0;
	answer_min_line_length = 0;
	cin >> board_size;
	for (y = 0; y < board_size; y++) {
		for (x = 0; x < board_size; x++) {
			cin >> board[y][x];
			if (board[y][x] == CELL_CORE && !is_on_edge(y, x)) {
				cores_x[n_cores] = x;
				cores_y[n_cores] = y;
				n_cores++;
			}
		}
	}
	solve_sub_problem(n_cores, 0, 0);
	printf("#%d %d\n", test_case_no, answer_min_line_length);
}

int main(int argc, char **argv)
{
	int T;
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin >> T;
	for (int test_case_no = 1; test_case_no <= T; ++test_case_no)
	{
		solve(test_case_no);
	}
	return 0;
}