[SW Expert Academy] 1767. 프로세서 연결하기

DFS를 이용하지만, 조건이 덧붙여져있어서,

return 되는 상황을 잘 생각해야하는 문제이다.

 

1) 전선이 연결된 코어 수는 최대가 되어야 하고,

2) 그 다음으로는, 전선 길이의 합이 최소가 되는 답을 찾으면 된다.

사실 이게 핵심이고, 나머지는 DFS이다.

 

 

#include <cstdio>
#include <cstring>
#include <vector>
#include <utility>

using namespace std;
int N;
int map_[12][12];
bool visited[12][12];
int dx[] = {-1, 1, 0, 0}, dy[] = {0, 0, -1, 1};
vector<pair<int,int> > cores;
int core_num;
int line_ans;

void go(int startidx, int line_len, int core_cnt){
    if (startidx == (int)cores.size()) {
        // 연결된 코어가 더 많은게 우선이다.
        if (core_cnt > core_num){
            core_num = core_cnt;
            line_ans = line_len;
        }
        else if (core_cnt == core_num && line_len < line_ans){
            line_ans = line_len;
        }
        return;
    }

    int x = cores[startidx].first;
    int y = cores[startidx].second;

    int temp[12][12];
    for (int i=0; i<N; ++i)
        for (int j=0; j<N; ++j)
            temp[i][j] = visited[i][j];

    for (int i=0; i<4; ++i){
        int nx = x + dx[i];
        int ny = y + dy[i];

        bool linechk = true;
        int temp_len = 0;
        while(1){
            if (0 > nx || nx >= N || 0 > ny || ny >= N) break;
            if (map_[nx][ny] == 1 || visited[nx][ny] == true) {
                linechk = false; break;
            }
            visited[nx][ny] = true;
            nx += dx[i];
            ny += dy[i];
            ++temp_len;
        }
        if (linechk) {
            go(startidx + 1, line_len + temp_len, core_cnt + 1);
        }

        if (temp_len > 0){
            for (int k=0; k<N; ++k)
                for (int h=0; h<N; ++h)
                    visited[k][h] = temp[k][h];
        }
            
    }
    go(startidx + 1, line_len, core_cnt);
}

int main() {
    int T;
    scanf("%d", &T);
    for (int t=1; t<=T; ++t) {
        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 && 
                    (0 < i && i < N - 1 && 0 < j && j < N - 1)){
                    cores.emplace_back(make_pair(i, j));
                }
            }
        }
        go(0, 0, 0);
        printf("#%d %d\n", t, line_ans);

        core_num = 0;
        line_ans = 0;
        memset(map_, 0, sizeof(map_));
        memset(visited, 0, sizeof(visited));
        cores.clear();
    }
    
    return 0;
}