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

https://www.swexpertacademy.com/main/code/problem/problemSolver.do

시뮬레이션 구현에 가까운 문제이다. 

완전 탐색 즉, DFS를 이용해서 core의 4방향으로 전선을 연결 할 수있는지 확인해보고 연결 후, 다른 코어들의 경우의 수를 따져 보았다. 

고려 사항 

1.  최대한 많은 Core에 전원을 연결해도, 전원이 연결되지 않는 Core가 존재할 수 있다. 

-> 생각을 조금만 해보면 굳이 연결 되지않는 Core에 대해 생각 안하고 4방향에 대한 조사만 해주어도 모든 경우를 따져 볼 수 있다는 사실을 알수 있다. 

2. Core의 개수는 최소 1개 이상 12개 이하이다.

-> 경우의 수는 최대 12^4가 나온다 . 

코드 

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int dx[4] = { 1,-1,0,0 };
int dy[4] = { 0,0,1,-1 };
int T, N;
int map[12][12];
struct  core
{
    int y, x;
};
vector <core> v;
int maxcore;
int minline;
void connect(int core, int n) // 연결된 코어 갯수,  검사한 코어 갯수 
{
    for (int r = 0; r < 4; r++) //4방향에 대해 연결 할 수 있는지 검사 
    {
        int x = v[n].x;
        int y = v[n].y;
        int flag = 0; // 연결 여부 판별 
        while (map[y + dy[r]][x + dx[r]] == 0)
        {
            y = y + dy[r];
            x = x + dx[r];
            if (y == 0 || x == 0 || y == N - 1 || x == N - 1)
            {
                flag = 1; 
                break;
            }
        }
        if (flag) // 맵 가장자리까지 방해물이 없다면 연결
        {
            x = v[n].x;
            y = v[n].y;
            while (map[y + dy[r]][x + dx[r]] == 0)
            {
                y = y + dy[r];
                x = x + dx[r];
                map[y][x] = 2;
                if (y == 0 || x == 0 || y == N - 1 || x == N - 1)
                {
                    core++;
                    break;
                }
            }
        }
        if (v.size() - 1 > n) // 모든 코어에 대한 검사를 안했다면 재귀 시작 
        {
            connect(core, n + 1);
        }
        else if (v.size() - 1 == n) // 모든 코어에 대한 검사 끝 
        {
            if (maxcore < core) // 현재 연결된 코어가 제일 큰 경우 
            {
                maxcore = core;
                int line = 0;
                for (int i = 0; i < N; i++)
                {
                    for (int j = 0; j < N; j++)
                    {
                        if (map[i][j] == 2)line++;
                    }
                }
                minline = line;
            }
            else if (maxcore == core) // 연결된 코어가 같은 경우 
            {
                int line = 0;
                for (int i = 0; i < N; i++)
                {
                    for (int j = 0; j < N; j++)
                    {
                        if (map[i][j] == 2)line++;
                    }
                }
                minline = min(minline, line);
            }
        }
        if (flag) // 연결 했던 전선을 다시 없애준다. 
        {
            x = v[n].x;
            y = v[n].y;
            while (map[y + dy[r]][x + dx[r]] == 2)
            {
                y = y + dy[r];
                x = x + dx[r];
                map[y][x] = 0;
                if (y == 0 || x == 0 || y == N - 1 || x == N - 1)
                {
                    core--;
                    break;
                }
            }
        }
        
    }
}
 
int main()
{
    //freopen("sample_input.txt", "r", stdin);
    scanf("%d", &T);
    vector <int> ans; 
    for (int testcase = 0; testcase < T; testcase++)
    {
        scanf("%d", &N);
        v.clear();
        minline = 0;
        maxcore = 0;
        for (int i = 0; i < N; i++)
        {
            for (int j = 0; j < N; j++)
            {
                scanf("%d", &map[i][j]);
                if(i!=0 && j!=0 && i!=N-1 && j!=N-1&&map[i][j]==1)
                {
                    v.push_back({ i,j });
                }
            }
        }
        connect(0, 0);
        ans.push_back(minline);
        for (int i = 0; i < N; i++)
        {
            for (int j = 0; j < N; j++)
            {
                map[i][j] = 0;
            }
        }
    }
    for (int i = 0; i < ans.size(); i++)
    {
        printf("#%d %d\n", i + 1 , ans[i]);
    }
    return 0;
}

while 문을 통해 코어를 연결 할수 있는지 검사를 했는데 이 부분을 함수로 만들어 처리했다면 좀 더 깔끔할 거같다.