[SWEA] 프로세서 연결하기

[SWEA] 프로세서 연결하기

Problem URL : 프로세서 연결하기

#include <iostream>
#include <vector>
#include <cstring>
#define p pair<int,int>
using namespace std;

int n, map[12][12];
int core, line, size;
int dx[] = { 0,1,0,-1 };
int dy[] = { 1,0,-1,0 };

vector<p> coreList;

int draw(int x, int y, int dir, bool drawMode) {
    int nx = x, ny = y;
    int add_line = 0;
    while (1) {
        nx = nx + dx[dir];
        ny = ny + dy[dir];
        if (0 > nx || nx >= n || 0 > ny || ny >= n) {
            break;
        }
        if (drawMode) {
            //전선을 map에 기록
            map[nx][ny] = 1;
            add_line++;
        } else {
            //전선을 map에서 삭제
            map[nx][ny] = 0;
        }
    }
    return add_line;
}

bool isEdge(int x, int y) {
    return (x == 0 || x == (n - 1) || y == 0 || y == (n - 1));
}

bool isDrawable(int x, int y, int dir) {
    while (1) {
        x = x + dx[dir];
        y = y + dy[dir];
        if (map[x][y]) {
            return false;
        }
        if (isEdge(x,y)) {
            return true;
        }
    }
}

void dfs(int idx, int _core, int _line) {
    if (idx == size) {
        if (_core > core) {
            core = _core;
            line = _line;
        }
        if (_core == core) {
            if (_line < line) {
                line = _line;
            }
        }
        return;
    }

    p current = coreList.at(idx);
    int x = current.first;
    int y = current.second;

    if (isEdge(x, y)) {
        dfs(idx + 1, _core + 1, _line);
    } else {
        for (int i = 0; i < 4; i++) {
            if (isDrawable(x,y,i)) {
                int add_line = draw(x, y, i, true); // 전선 그리기
                dfs(idx + 1, _core + 1, _line + add_line);
                draw(x, y, i, false); // 전선 지우기
            }
        }
        dfs(idx + 1, _core, _line);
    }
}

int main() {
    int tc;
    cin >> tc;

    for (int TC = 1; TC <= tc; TC++) {
        core = 0;
        line = 2e9;
        memset(map, 0, sizeof(map));
        coreList.clear();
        cin >> n;

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                int tmp;
                scanf("%d", &tmp);
                if (tmp) {
                    map[i][j] = tmp;
                    coreList.push_back({i,j});
                }
            }
        }

        size = (int)coreList.size();
        dfs(0, 0, 0);
        printf("#%d %d\n", TC, line);
    }
    return 0;
}