[SWExpertAcademy_1767(프로세서 연결하기 )]

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

 

문제 설명

문제를 무단 복제하는 것을 금지하기 때문에 들어가서 확인 해 보시길 !

• 7 ≤ N ≤ 12, Core의 개수는 최소 1개 이상 12개 이하이다.
• 최대한 많은 Core에 전원을 연결하였을 경우, 전선 길이의 합을 구하는 문제
• Core는 모두 연결되지 않을 수도 있다.

문제 풀이

• Core의 숫자가 12 이하이기때문에 인접한 칸(4칸)을 모두 탐색해도 시간 초과가 나지 않는다.
• 재귀를 사용하여 모든 Core를 연결하여 최대 Core일때, 최소 전선 길이를 구한다.

문제 순서

1. Core의 좌표를 저장한다.
   • i == 0 || i == N - 1 || j == 0 || j == N - 1 일 경우를 제외(이미 연결 되있기 때문)
2. 저장한 Core의 좌표를 재귀로 탐색한다.
   1. 전선 그리기
      • 현재 Core의 좌표의 상하좌우를 탐색한다.
      • 만일 이동할 수 있으면,전선을 연결하고(p[i][j]=2로),전선 길이 카운팅한다.
      • 다음 Core로 넘어간다.
      • 재귀 종료 후에 연결 된 전선을 초기화한다.
   2. 전선의 길이
      • 현재 연결된 코어가 이전 보다 크다면, 전선의 총길이를 저장한다
      • 만일 코어 수 가 같다면, 작은 전선 길이를 저장한다.
      • (현재 연결된 수+남은 연결 전선 수)가 기존 core보다 작다면 답이 되지 않으니 종료

 

 

 

 

 

 

#include <iostream>
#include <vector>
using namespace std;

int p[13][13];
int N;

vector<pair<int, int> > v;

bool check(int x, int y) //범위 체크
{

    if (x >= 0 && x < N && y >= 0 && y < N)
    {
        return true;
    }
    else
    {

        return false;
    }
}

int dx[] = {-1, 1, 0, 0};
int dy[] = {0, 0, -1, 1};

bool connected_check(int x, int y, int k)
{
    //연결 가능한지 확인하는 함수

    while (true)
    {

        int nx = x + dx[k];
        int ny = y + dy[k];

        if (!check(nx, ny)) //범위를 넘어갈때까지 전선 연결 가능
        {

            break;
        }

        if (p[nx][ny]) //중간에 전선이 있어서 연결 불가한 경우
        {

            return false;
        }
        x = nx;
        y = ny;
    }

    return true;
}

int draw(int x, int y, int k)
{

    int count = 0; //전선길이 카운팅

    while (true)
    {

        int nx = x + dx[k];
        int ny = y + dy[k];

        if (!check(nx, ny))
        {

            break;
        }

        p[nx][ny] = 2; //2로 코어와 구분

        x = nx;
        y = ny;
        count++;
    }

    return count;
}

void init(int x, int y, int k)
{

    //연결한 전선 초기화
    while (true)
    {

        int nx = x + dx[k];
        int ny = y + dy[k];

        if (!check(nx, ny))
        {

            break;
        }

        p[nx][ny] = 0;

        x = nx;
        y = ny;
    }
}

int core = 0;

int ans = 0;

void go(int cnt, int start, int value)
{

    if (core > cnt + (v.size() - start))
    {
    // (현재 연결된 수+남은 연결 전선 수)가 기존 core보다 작다면 답이 되지 않으니 종료

        return;
    }

    if (core < cnt) //코어가 더 클때
    {

        core = cnt;
        ans = value; //전선 길이 저장
    }
    else if (core == cnt)

    {
        //같다면, 최솟값 업데이트
        ans = min(value, ans);
    }

    for (int i = start; i < v.size(); i++)
    {
        int x = v[i].first;
        int y = v[i].second;

        for (int k = 0; k < 4; k++)
        {
            //상하 좌우 탐색

            if (connected_check(x, y, k))
            {
                //연결 가능하면

                int count = draw(x, y, k);
                //전선 연결 그림

                go(cnt + 1, i + 1, value + count);
                //재귀 진행

                init(x, y, k);
                //연결한 전선 초기화
            }
        }
    }
}

int main(int argc, char **argv)
{
    int test_case;
    int T;

    cin >> T;

    for (test_case = 1; test_case <= T; ++test_case)
    {

        cin >> N;
        v.clear();
        core = 0;
        ans = 0;

        for (int i = 0; i < N; i++)
        {

            for (int j = 0; j < N; j++)
            {
                cin >> p[i][j];
                if (p[i][j])
                {

                    if (!(i == 0 || i == N - 1 || j == 0 || j == N - 1))
                    {
                        //양 끝 지점에 있을 때를 제와하고 좌표값 넣음
                        v.push_back(make_pair(i, j));
                    }
                }
            }
        }

        go(0, 0, 0);

        cout << "#" << (test_case) << " " << ans << '\n';
    }
    return 0;
}