[SWEA 1767] 프로세서 연결하기 (C++)

문제 링크: https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV4suNtaXFEDFAUf

SW Expert Academy

1. 주의할 점

- 해당 위치의 코어를 가장자리와 연결 하지 않는 경우도 있다

- 새로운 방법으로 더 많은 코어가 연결 가능하다면, 무조건 MaxConnect, Minlen을 갱신한다

- 매 TC마다 V벡터, MaxConnect, Minlen를 초기화한다

 

2. 구현

- 변두리에 위치하지 않은 코어를 V 벡터에 전부 넣는다

- 코어를 가장 자리와 연결할 수 있는지 확인하고, 가능하다면 Arr[][]배열에는 전선을 표시하기 위해 2를 대입한다

- 4방향 모두 검사하며, 연결하지 않고 다른 코어로 넘어가는 경우도 추가한다

- 만약 Idx가 V 벡터의 크기와 같다면 MaxConnect와 Minlen을 모두 Len, Conn과 비교하며 갱신이 필요한 경우, 갱신한다

 

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int dx[4] = { 0,1,0,-1 };
int dy[4] = { -1,0,1,0 };
struct info {
	int x, y;
};
info tmp;
vector<info> v;
int num, maxConnect, minlen;
int arr[12][12];

void dfs(int idx, int len, int conn) {
	if (idx == v.size()) {
		if (conn > maxConnect) {
			minlen = len;
			maxConnect = conn;
		}
		else if (conn == maxConnect) 
			minlen = min(minlen, len);		
		return;
	}
	for (int i = 0; i < 4; i++) {
		int nx = v[idx].x;
		int ny = v[idx].y;
		int cnt = 0;
		while (1) {
			nx += dx[i];
			ny += dy[i];
			cnt++;
			if (arr[ny][nx] == 1 || arr[ny][nx] == 2) {
				cnt = 0;
				break;
			}
			if (arr[ny][nx]==0 && (nx == 0 || ny == 0 || nx == num - 1 || ny == num - 1)) {
				break;
			}
		}
		if (cnt > 0) {
			nx = v[idx].x;
			ny = v[idx].y;
			while (1) {
				nx += dx[i];
				ny += dy[i];
				if (nx < 0 || ny < 0 || nx > num - 1 || ny > num - 1)
					break;
				arr[ny][nx] = 2;
			}
			dfs(idx + 1, len + cnt, conn + 1);
			nx = v[idx].x;
			ny = v[idx].y;
			while (1) {
				nx += dx[i];
				ny += dy[i];
				if (nx < 0 || ny < 0 || nx > num - 1 || ny > num - 1)
					break;
				arr[ny][nx] = 0;
			}
		}
	}
	dfs(idx + 1, len, conn);
}

int main() {
	int test;
	cin >> test;
	for (int t = 1; t <= test; t++) {
		cin >> num;
		v.clear();
		for (int i = 0; i < num; i++)
			for (int j = 0; j < num; j++) {
				cin >> arr[i][j];
				if (arr[i][j] == 1) {
					//외곽은 무시
					if (i == 0 || i == num - 1 || j == 0 || j == num - 1) continue;
					tmp.x = j;
					tmp.y = i;
					v.push_back(tmp);
				}
			}
		maxConnect = 0;
		minlen = 987654321;
		dfs(0, 0, 0);
		cout << "#" << t << " " << minlen << '\n';
	}
	system("pause");
	return 0;
}