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

[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);
    }
}