문제

문제링크 (로그인해야함)

SW Expert Academy 문제다.

그래프에서 코어가 상하좌우 한곳으로 길게 이어지는데
이때 코어수는 최대갯수면서 이어지는 선분의 길이의 합이 최소가 되게하는게 문제다.

풀이

나는 다음과 같이 알고리즘 순서를 매겼다.

1. 5가지 방법으로 트리를 만든다. (동서남북,pass)
   코어가 동서남북으로 길게 뻗거나 그냥 넘어가는 것이다.
2. 진행해도 되는지 check한다.
   단순하게 앞에 코어가 있는지 확인
3. 진행해도 되면 연결한다.
   check처럼 진행하는데 이번엔 1로 체크해준다.
4. bfs를 통해 다음 core 순서로 넘어간다.
   마지막 코어까지 도달하면 사용한 코어수와 길이의 합을 저장해준다.
5. bfs를 끝내면 연결을 다시 지운다.(3번을 없애주는 역할)

result 결과 수 문제

빅오를 생각해보면 5가지 방법으로 뻗어나가니 5^n(코어의 수)이 나오게 된다. 그래서 처음 작성한 코드의 결과를 확인해보니 결과수가 너무 많이 나왔다.

코어가 9개니까 5^9=1953125 개 까지도 결과가 나올수가 있다.

굳이 모든 결과를 다 비교해야하나 싶었다.

예를 들어 코어 6개까지 진행했는데 코어수는 2개면 9개까지 진행해도 2+3 = 5개가 최대가 될게 뻔한데 굳이 나머지를 진행해야하나 싶었다.

그래서 최대 코어수를 저장해주고 앞으로 코어수를 늘리면 최대 코어수를 갱신할 수 있는것들만 진행해줬다.

if (cores.size()-coreIdx+coreNum<maxCore) return;

필요없는 가지를 제거해줬더니 경우의 수가 많이 줄었다.

제출할때 다른 사람들 코드 길이가 보여서 봤는데 내껀 좀 길어보였다. 최대한 헷갈리지 않게 코딩하다는걸 목표로하니 코드가 조금 길어진 감이 있다.

code

/**
 * SW Test 샘플문제
 * 프로세서 연결하기
*/
#include <bits/stdc++.h>
#define INF 1e9
using namespace std;

int n;
int graph[12][12];
vector<pair<int,int>> cores;
vector<pair<int,int>> result; // {core수,-길이}
int maxCore=0;

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

bool check(int di,int y,int x){
    // 방향 검사
    int my=y;
    int mx=x;
    while(true){
        my+=dy[di];
        mx+=dx[di];

        if(my<0 || my>=n || mx<0 || mx>=n) return true;
        else if(graph[my][mx]==1) return false;
    }
}

int connect(int di,int y,int x){
    // 연결하기
    int sum=0;
    int my=y;
    int mx=x;
    while(true){
        my+=dy[di];
        mx+=dx[di];

        if(my<0 || my>=n || mx<0 || mx>=n) return sum;
        else{
            graph[my][mx]=1;
            sum++;
        }
    }
}

void deconnect(int di,int y,int x){
    // 연결해제
    int my=y;
    int mx=x;
    while(true){
        my+=dy[di];
        mx+=dx[di];

        if(my<0 || my>=n || mx<0 || mx>=n) return;
        else{
            graph[my][mx]=0;
        }
    }
}

void dfs(int coreIdx,int coreNum,int sum){
    // maxCore 고려해보기
    if (cores.size()-coreIdx+coreNum<maxCore) return;

    // 마지막 체크
    if (coreIdx==cores.size() && coreNum>=maxCore){
        maxCore=coreNum;
        result.push_back({-coreNum,sum});
        return;
    }

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

    // 동서남북
    for(int di=0;di<4;di++){
        if(check(di,y,x)){
            int connectSum=connect(di,y,x);
            dfs(coreIdx+1,coreNum+1,sum+connectSum);
            deconnect(di,y,x);
        }
    }
    // pass
    dfs(coreIdx+1,coreNum,sum);
}

int main(void){
    int tc;
    int cnt=0;
    cin>>tc;
    while(tc--){
        cin>>n;
        cores.clear();
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                scanf("%d",&graph[i][j]);
                if(graph[i][j]==1){
                    cores.push_back({i,j});
                }
            }
        }
        // 5가지 상태로 dfs 동,서,남,북,패스
        int y=cores.front().first;
        int x=cores.front().second;

        result.clear();
        maxCore=0;
        // 동서남북    
        for(int di=0;di<4;di++){
            if(check(di,y,x)){
                int sum=connect(di,y,x);
                dfs(1,1,sum);
                deconnect(di,y,x);
            }    
        }
        // pass
        dfs(1,0,0);
        if (result.empty()){
            cout<<"#"<<++cnt<<" result empty"<<endl;
        }
        else{
            sort(result.begin(),result.end());
            cout<<"#"<<++cnt<<" "<<result.front().second<<endl;
            //cout<<"result size : "<<result.size()<<endl;
        }
    }
    return 0;
}