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

막혔던 점

-처음에는 dfs로 모든 core마다 방향을 정하고 bfs로 하려고 했으나 시간 초과

 

해결책

-dfs로 모든 core마다 4방향마다 연결가능할 때->전선표시->dfs(idx+1,coreDone+1)->전선초기화

                                          연결 불가능할 때->dfs(idx+1,coreDone)

 

주의할 점

-무조건 answer을 최소값으로 갱신하는 것이 아니다.

maxDone을 갱신할 때 기존의 answer이 temp보다 더 작을 수 있다.

그래서 maxDone이 같을 때만 최소값으로 갱신한다.

 

#include <iostream>
#include <vector>
using namespace std;
int T, N;
int coreNum;
int maxDone;
int cell[13][13];
int answer;

void dfs(int count, int done, vector<pair<int, int>> v) {
    if (count == coreNum) {
        int temp = 0;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (cell[i][j] == 2)
                    temp++;
            }
        }
        if(done>maxDone){
            maxDone=done;
            answer=temp;
        }
        else if(done==maxDone)	answer=answer<temp?answer:temp;
        return;
    }

    int y = v[count].first;
    int x = v[count].second;

    if (y == 0 || y == N - 1 || x == 0 || x == N - 1)
        dfs(count + 1, done + 1, v);
    else {

        //상
        bool flag = true;
        for (int i = 0; i < y; i++) {
            if (cell[i][x] != 0) {
                flag = false;
                break;
            }
        }
        if (flag) {
            for (int i = 0; i < y; i++) {
                cell[i][x] = 2;
            }
            dfs(count + 1, done + 1, v);
            for (int i = 0; i < y; i++) {
                cell[i][x] = 0;
            }
        }
        //하
        flag = true;
        for (int i = y + 1; i < N; i++) {
            if (cell[i][x] != 0) {
                flag = false;
                break;
            }
        }
        if (flag) {
            for (int i = y + 1; i < N; i++)
                cell[i][x] = 2;
            dfs(count + 1, done + 1, v);
            for (int i = y + 1; i < N; i++)
                cell[i][x] = 0;
        }

        //좌
        flag = true;
        for (int i = 0; i < x; i++) {
            if (cell[y][i] != 0) {
                flag = false;
                break;
            }
        }
        if (flag) {
            for (int i = 0; i < x; i++)
                cell[y][i] = 2;
            dfs(count + 1, done + 1, v);
            for (int i = 0; i < x; i++)
                cell[y][i] = 0;
        }

        //우
        flag = true;
        for (int i = x + 1; i < N; i++) {
            if (cell[y][i] != 0) {
                flag = false;
                break;
            }
        }
        if (flag) {
            for (int i = x + 1; i < N; i++)
                cell[y][i] = 2;
            dfs(count + 1, done + 1, v);
            for (int i = x + 1; i < N; i++)
                cell[y][i] = 0;
        }

        dfs(count + 1, done, v);
    }
}

int main(void) {
    cin >> T;
    for (int casenum = 1; casenum <= T; casenum++) {
        cin >> N;

        vector<pair<int, int>> core;
        coreNum = 0;
        maxDone = 0;
        answer = 200;
        for (int i = 0; i < N; i++)
            for (int j = 0; j < N; j++)
                cell[i][j] = 0;

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                cin >> cell[i][j];
                if (cell[i][j] == 1) {
                    coreNum++;
                    core.push_back({ i,j });
                }
            }
        }

        dfs(0, 0, core);

        cout << "#" << casenum << " " << answer << "\n";
    }
}