[C++] 삼성 1767. [SW Test 샘플문제] 프로세서 연결하기

#include <iostream>
#include <algorithm>
#include <vector>
 
using namespace std;
 
int arr[12][12];
int T, N, res, pnum;
 
bool dir_check(int x, int y, int dir) {
    if (dir == 1) {
        for (int i = y + 1; i < N; i++) {
            if (arr[x][i] != 0)
                return false;
        }
    }
    else if (dir == 2) {
        for (int i = x + 1; i < N; i++) {
            if (arr[i][y] != 0)
                return false;
        }
    }
    else if (dir == 3) {
        for (int i = 0; i < y; i++) {
            if (arr[x][i] != 0)
                return false;
        }
    }
    else {
        for (int i = 0; i < x; i++) {
            if (arr[i][y] != 0)
                return false;
        }
    }
    return true;
}
 
int dir_line(int x, int y, int dir, int flag) {
    int ans = 0;
    if (dir == 1) {
        for (int i = y + 1; i < N; i++) {
            arr[x][i] = (flag == 0) ? 2 : 0;
            ans++;
        }
    }
    else if (dir == 2) {
        for (int i = x + 1; i < N; i++) {
            arr[i][y] = (flag == 0) ? 2 : 0;
            ans++;
        }
    }
    else if (dir == 3) {
        for (int i = 0; i < y; i++) {
            arr[x][i] = (flag == 0) ? 2 : 0;
            ans++;
        }
    }
    else {
        for (int i = 0; i < x; i++) {
            arr[i][y] = (flag == 0) ? 2 : 0;
            ans++;
        }
    }
    return ans;
}
 
void dfs(vector<pair<int, int>> &v, int index, int num, int line) {
    if (index == v.size()) {
        if (pnum < num) {
            res = line;
            pnum = num;
        }
        else if (pnum == num) {
            if (res > line) res = line;
        }
    }
    else {
        for (int i = 1; i <= 4; i++) {
            if (dir_check(v[index].first, v[index].second, i)) {
                dfs(v, index + 1, num + 1, line + dir_line(v[index].first, v[index].second, i, 0));
                dir_line(v[index].first, v[index].second, i, 1);
            }
        }
        dfs(v, index + 1, num, line);
    }
}
 
int main() {
    cin >> T;
    for (int tc = 1; tc <= T; tc++) {
        vector<pair<int, int>> v;
        cin >> N;
 
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                cin >> arr[i][j];
                if (i == 0 || j == 0 || i == N - 1 || j == N - 1) continue;
 
                if (arr[i][j] == 1) {
                    v.push_back(pair<int, int>(i, j));
                }
            }
        }
 
        res = 987654321;
        pnum = 0;
        dfs(v, 0, 0, 0);
        cout <<"#"<< tc << " " << res << endl;
    }
}