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

* dfs 조합을 이용해서 최대한 많은 core들을 연결했을 때 최소 전선의 길이를 구한다. 

* 맵의 사이드에 있는 코어들은 이미 연결되어있기 때문에 cores에는 그 외의 코어들을 넣는다. 

* dfs(idx, cnt)에서는 코어들을 조합을 확인하면서 백트래킹한다. 

*

check(x, y, d) : x, y 좌표에 있는 코어가 d방향으로 연결될 수 있으면 T, 아니면 F

doConnect(x, y, d) : check() 가 T라면 연결한다. (chk 배열에 방문표시)

doDisConnect(x, y, d) : 원상 복귀 (백트래킹)

 

 

 

#include <iostream> #include <vector> #include <cstring> #define INF 987654321 using namespace std; int n; int map[13][13]; bool connected[13]; int dx[4] = {-1, 1, 0, 0}, dy[4] = {0, 0, -1, 1}; bool chk[13][13]; int ans = 0, length = INF; typedef pair<int, int> pp; vector<pp> cores; //연결된 코어를 저장 int min(const int &a, const int &b) { if (a < b) return a; return b; } bool check(int x, int y, int d) { //이 방향으로 이어질 수 있는지 확인한다. while (1) { x += dx[d]; y += dy[d]; if (x < 0 || x >= n || y < 0 || y >= n) break; if (map[x][y] || chk[x][y]) return false; } return true; } void doConnect(int x, int y, int d) { //방문 표시 while (1) { x += dx[d]; y += dy[d]; if (x < 0 || x >= n || y < 0 || y >= n) break; chk[x][y] = true; } } void doDisConnect(int x, int y, int d) { while (1) { x += dx[d]; y += dy[d]; if (x < 0 || x >= n || y < 0 || y >= n) break; chk[x][y] = false; } } int calc() { int len = 0; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (chk[i][j]) len++; } } return len; } void dfs(int idx, int cnt) { if (idx == cores.size()) { if (ans < cnt) { ans = cnt; length = calc(); } else if (ans == cnt) { length = min(length, calc()); } return; } for (int i = idx; i < cores.size(); i++) { if (!connected[i]) { int x = cores[i].first; int y = cores[i].second; for (int d = 0; d < 4; d++) { if (check(x, y, d)) { doConnect(x, y, d); connected[i] = true; dfs(i+ 1, cnt + 1); connected[i] = false; doDisConnect(x, y, d); } } } } } void init() { memset(chk, 0, sizeof(chk)); memset(connected, 0, sizeof(connected)); ans = 0; length = 0; cores.clear(); } int main() { ios_base::sync_with_stdio(0); cin.tie(0); int t; cin >> t; for (int tc = 1; tc <= t; tc++) { init(); cin >> n; int cnt = 0; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { cin >> map[i][j]; if (map[i][j]) { if (i == 0 || j == 0 || i == n - 1 || j == n - 1) { cnt++; } else cores.push_back(pp(i, j)); } } } //가장자리에 있는 core는 이미 연결되어있다. dfs(0, 0); cout << "#" << tc << " " << length << '\n'; } return 0; }