CS/Algorithm
[SWEA][C++] 1767 프로세서 연결하기
별토끼.
2019. 3. 7. 15:36
반응형
[SWEA][C++] 1767 프로세서 연결하기
문제
SW Expert Academy 1767 프로세서 연결하기
풀이
처음에 풀었을 때 시간초과가 나서 다시 풀었던 문제 입니다.
구조체를 이용해서 벽 근처에 있는 경우와 아닌 경우를 구분해서 입력을 받아요.
이후 DFS를 이용해서 답을 구하는데 코어 위치에서 네 방향 모두 node를 놓고 연결이 될 경우 다음 node로 넘어가도록 합니다. 사방이 막힌 경우는 그냥 넘어갈 수 있도록 변수 하나를 놓고 체크하도록 해야 합니다. 안그러면 마지막 테스트 케이스가 넘어가지 않더라구요.
node를 놓는 과정에서 몇 개를 놓는지 체크할 필요가 있는데 이건 참조변수를 이용했습니다. 갯수를 다른 node에 부딪히거나 다른 core에 부딪히면 이 값을 이용해 node를 회수하도록 합니다.
코드
#define _CRT_SECURE_NO_WARNINGS
#define MAX 987654321
#include <cstdio>
#include <vector>
using namespace std;
typedef struct Core{
int x, y;
bool wall;
Core() {}
Core(int _x, int _y, int _wall) : x(_x), y(_y), wall(_wall) {}
};
int n;
int max_core = 0, min_node = MAX;
bool connect_node(int x, int y, int dx, int dy, int node, int (*map)[12], int &node_num, int remove) {
int val = 0;
while (true) {
x += dx;
y += dy;
//벽에 연결될 경우
if (x < 0 || y < 0 || x >= n || y >= n) break;
//연결가능 여부 확인
if (node == -1) {
//core이거나 node
if (map[x][y] == 1 || map[x][y] == -1) return false;
}
//node 회수
if(node == 1) {
if (val == remove) return false;
}
map[x][y] += node;
node_num = val = (val + 1);
}
return true;
}
void DFS(vector<Core> cores, int connect, int core_cnt, int (*map)[12], int node) {
if (core_cnt == cores.size()) {
if (max_core <= connect) {
if (connect == max_core) min_node = (node < min_node ? node : min_node);
else {
max_core = connect;
min_node = node;
}
}
return;
}
if (cores[core_cnt].wall) { //벽에 붙어있는 경우
DFS(cores, connect + 1, core_cnt + 1, map, node);
}
else {
int dx[] = { 1,-1,0,0 };
int dy[] = { 0,0,1,-1 };
int ncnt = 0;
for (int i = 0; i < 4; i++) {
int x = cores[core_cnt].x;
int y = cores[core_cnt].y;
int node_num = 0;
//연결된 경우
if (connect_node(x, y, dx[i], dy[i], -1, map, node_num, 0)) {
DFS(cores, connect + 1, core_cnt + 1, map, node + node_num);
}
//연결 안된 경우
else
ncnt++;
//전선 복구
connect_node(x, y, dx[i], dy[i], 1, map, node_num, node_num);
//사방이 막힌 경우
if (ncnt == 4) {
DFS(cores, connect, core_cnt + 1, map, node);
}
}
}
}
int main() {
int T;
scanf("%d", &T);
for (int t = 1; t <= T; t++) {
int map[12][12];
vector<Core> cores;
scanf("%d", &n);
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
scanf("%d", &map[i][j]);
//코어일 경우
if (map[i][j] == 1) {
//벽에 붙은 경우 체크
if (i == 0 || j == 0 || i == n - 1 || j == n - 1) {
cores.push_back(Core(i, j, true));
}
else
cores.push_back(Core(i, j, false));
}
}
}
max_core = 0;
min_node = MAX;
DFS(cores, 0, 0, map, 0);
printf("#%d %d\n", t, min_node);
}
}
반응형