#1767. [SW Test 샘플문제] 프로세서 연결하기

출처:https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV4suNtaXFEDFAUf

SW Expert Academy

 

풀이

dfs를 통해 구현.

가장자리에 붙어있는 프로세서는 무조건 전선길이가 0이므로 제외를 시켜준다. 그리고 나머지 프로세서들 중에서 전선배치를 완전탐색으로 구현하였다. 그냥 전선을 설치하지 않고 넘어가거나 각 방향별로 전선을 설치한 후 다음 dfs로 넘겨주는 방식으로 구현하였다. 전선을 설치하지 않을시 realcnt를 증가시키지 않고, turn횟수인 cnt값만 증가시켰으며

전선을 설치시 cnt와 realcnt를 모두 증가시켰다. 그리고 dfs입력 변수로 현재까지 설치한 전선 길이의 합을 계속해서 다음턴으로 넘겨준다. 그래서 cnt값이 총 프로세서개수와 같아지면 각 realcnt에 대한  전선길이 최솟값을 저장하는 배열에 그 값을 최솟값으로 갱신시켜서 보관한다. 그리고 시간초과를 줄이는 핵심이 있다. 여태까지 연결시킨 프로세서 수 + 앞으로 남은 프로세서 개수가 과거에 탐색을 완료했던 realcnt의 최댓값보다 작으면 탐색을 할필요가 없으므로 리턴시켜주면 시간을 10배 이상 줄일 수 있다.

 

코드

 

	// #s1767 프로세서 연결하기
	#include <iostream>
	#include <algorithm>
	#include <cstring>
	#include <vector>
	#define INF 100000000
	using namespace std;
	int dir[4][2] = { {1,0}, { 0,1 }, { -1,0 }, { 0,-1 } };
	// 노드 선을 연결안하고 그냥 스킵하거나 , 선 연결하돼 가능한 곳만 연결
	int map[12][12];
	int visit[12][12];
	int n;
	int node_size;//가장자리 프로세서를 제외한 노드 수
	int ans[13];
	int realmax = 0;
	typedef struct xy {
	int x, y;
	};
	vector <xy> node;
	bool check(xy temp,int d) {
	int fx = temp.x, fy = temp.y;
	while (true) {
	fx += dir[d][0], fy += dir[d][1];
	if (fx < 0 || fy < 0 || fx >= n || fy >= n)return true;
	if (map[fx][fy] || visit[fx][fy])return false;
	}
	}
	int fill_visit(xy temp, int d, bool tf) {
	int fx = temp.x, fy = temp.y;
	int sum = 0;
	while (true) {
	fx += dir[d][0], fy += dir[d][1];
	if (fx < 0 || fy < 0 || fx >= n || fy >= n) {
	return sum;
	}
	visit[fx][fy] = tf;
	sum++;
	}
	}
	void dfs(int cnt,int realcnt,int sum) {
	if (realmax > realcnt + (node_size - cnt))return;
	if (cnt == node_size) {
	ans[realcnt] = min(ans[realcnt], sum);
	realmax = max(realmax, realcnt);
	return;
	}
	// 만약 노드 선 연결 가능하면 realcnt값 증가, cnt는 그냥 증가,
	// check 를 통해 연결 가능한지 확인부터 하고 연결가능하면 fillvisit로 채워넣기
	xy temp = node[cnt];
	for (int d = 0; d < 4; d++) {
	if (!check(temp, d))continue;
	int temp_sum =fill_visit(temp, d, true);
	dfs(cnt + 1, realcnt + 1,sum+temp_sum);
	fill_visit(temp, d, false);
	}
	dfs(cnt + 1, realcnt,sum);
	}
	void Input() {
	memset(visit, 0, sizeof(visit));
	memset(map, 0, sizeof(map));
	fill(ans, ans + 13, INF);
	node.clear();
	realmax = 0;
	cin >> n;
	for (int i = 0; i < n; i++) {
	for (int j = 0; j < n; j++) {
	cin >> map[i][j];
	if (map[i][j] && !(i == 0 || j == 0 || i == n - 1 || j == n - 1)) {
	node.push_back({ i,j });
	}
	}
	}
	node_size = node.size();
	}
	int main() {
	int test;
	cin >> test;
	for (int t = 1; t <= test; t++) {
	Input();
	dfs(0, 0, 0);
	for (int i = 12; i >= 0; i--) {
	if (ans[i] != INF) {
	cout << "#" << t << " " << ans[i] << endl;
	break;
	}
	}
	}
	}

view raw [SWEA]1767 프로세서 연결하기.cpp hosted with ❤ by GitHub