[삼성 sw 역량 테스트 A형 샘플 문제] 프로세서 연결하기 c++

 

 

dfs로 전선 연결이 필요한 모든 프로세서 들이 전설을 이을 모든 경우의 수를 따져서 구했다. 여기서, 만약 해당 프로세서가 벽으로 도달하지 못하는 경우를 계산하여 백트래킹( 가지치기) 를 수행하였다. 

 

추가로, 이 문제에선,'모두 연결 가능 할시의 최단 거리' 가 아니라, '최대한 많은 개수를 연결할 시 의 최단거리' 를 구해야한다. 따라서, dfs를 통해 해당 프로세서를 '상','하','좌','우' 로 연결하는 가능성에 더해, '해당 프로세서를 연결하지 않는 가능성' 도 체크해야한다. 

 

 

예시

 

위와 같이 입력이 들어온 경우, 우리가 전선으로 연결해줘야하는, 파란 동그라미 표시를한 프로세서에 대해 전선의 연결 가능성을 확인해야한다. 하지만, 맨위의 파랑 원은, 다른 전선들이 연결되면, 필연적으로 벽에 닿을 수 없게 된다.

 

이 경우, '모든 프로세서를 연결' 하는 것은 불가하다. 따라서, 최대한 많은 프로세서를 연결하고, 그 상황에서의 최단 거리를 찾으면 된다. 따라서, 위의 빨간 화살표와 같이, 6의 길이의 전선을 사용해 2개의 프로세서를 연결하는 것이 최선이다. 

 

 

 

따라서, dfs를 통해 아래와 같이 분기를 체크하며 재귀를 수행하여 모든 경우의 수를 구한 뒤, 그 중 조건을 만족하는 값을 찾으면 된다.

[위로 연결, 아래로 연결, 왼쪽으로 연결, 오른쪽으로 연결, 연결 x]

 

 

 

#include<iostream>
#include<vector>
#include<queue>
using namespace std;
#include<string.h>
#define INF 9876543
int visit[30][30];
int arr[30][30];
int dw[4] = { 1,-1,0,0 };
int dh[4] = { 0,0,1,-1 };
int t, n;

vector<pair<int, int>> point;

int max_depth = 0;

int minArr[100];

void dfs(int depth,int dist,int idx) {//depth: 연결한 프로세서 수, idx: 현재 체크할 프로세서 번호
	if (minArr[depth] > dist)minArr[depth] = dist;

	if ( depth == point.size()||idx== point.size()) {
		return;
	}

	for (int i = 0; i < 4; i++) { //idx번째 프로세서의 상,하,좌,우 분기 체크
		int nw = point[idx].first, nh = point[idx].second;
		int len = 0;
		
		while (arr[nw + dw[i]][nh + dh[i]] == 0) {
			
			nw += dw[i];
			nh += dh[i];
			len++;
			arr[nw][nh] = 3;
		}
		if (nw == 1 || nh == 1 || nw == n || nh == n) {
			dfs(depth + 1, dist + len, idx+1);
		}
		while (arr[nw][nh] ==3) {
			arr[nw][nh] = 0;
			nw -= dw[i];
			nh -= dh[i];
		}
	}
	dfs(depth, dist, idx+1); //idx번째 프로세서를 선택하지 않는 분기
}

int main() {
	cin >> t;
	int cnt = 0;
	while (cnt++<t) {
		cin >> n;
		memset(arr, -1, sizeof(int) * 30 * 30);
		memset(visit, -1, sizeof(int) * 30 * 30);
		for (int i = 0; i < 100; i++)minArr[i] = INF;
		vector<pair<int, int>> tmp;
		point = tmp;
		
		max_depth=0;
		//0:빈칸, 1: 연결해야할 놈, 2: 이미연결된놈(장애물) 3: 전선
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				cin >> arr[i][j];
				if (arr[i][j]==1&&(i == 1 || j == 1||i==n||j==n)) arr[i][j] = 2;
				if (arr[i][j] == 1)
					point.push_back({ i,j });
			}
		}
		
		dfs(0, 0,0);
		int min_dist = -1;
		for (int i = point.size(); i >= 0; i--) {
			if (minArr[i] != INF) {
				min_dist = minArr[i];
				break;
			}
		}
		printf("#%d %d\n", cnt,min_dist);
	}
	return 0;
}