1767 프로세서 연결하기

https://www.swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV4suNtaXFEDFAUf

Core의 개수가 최대 12개 이므로 각각의 Core에 대해서 4가지 방향의 모든 경우의 수를 만들면 된다. 최대 4^12=16777216 이므로 시간 초과에 대해서는 걱정할 필요가 없음을 알 수 있다. 각 경우에 대해서 가장자리에 있는 코어는 어차피 전원에 연결되 있으므로 따로 카운트 해주고 나머지 코어들에 대해서 정해진 방향으로 전선을 만들어 보면서 기존의 코어나 전선과 겹치는 것이 없는지 확인한다. 그리고 정답을 갱신해 갈 때 Core의 개수, 전선 길이의 합 순으로 우선순위를 두어서 한다. 또한 테스트케이스가 여러 개이므로 전역변수들에 대하여 초기화를 꼭 해줘야함에 주의하자.

삼성 SW Test A형과 코딩테스트의 특징이 보통 시간에 대해서는 크기를 작게 해서 최적화나 특정 알고리즘 사용에 대해서는 고려하지 않아도 되고 주로 완전탐색을 통해 구현을 할 수 있느냐를 물어보는 것 같다.

#include <cstdio>
#include <vector>
using namespace std;
 
int t,n,map[12][12],cnt,cnt2,dx[4]={0,0,1,-1},dy[4]={1,-1,0,0},CORE,SUM;
vector<pair<int,int>> core;
vector<int> v;
 
void solve()
{
    int tmap[12][12];
    for(int i=0;i<n;i++) for(int j=0;j<n;j++) tmap[i][j]=map[i][j];
    int sum=0,c=cnt2;
    for(int i=0;i<cnt;i++)
    {
        int x=core[i].first,y=core[i].second;
        while(true)
        {
            x+=dx[v[i]],y+=dy[v[i]];
            if(x<0 || x>=n || y<0 || y>=n) { c++; break; }
            if(tmap[x][y]==1) return;
            else tmap[x][y]=1,sum++;
        }
    }
    if(CORE<c) CORE=c,SUM=sum;
    else if(CORE==c && SUM>sum) SUM=sum;
}
 
void go(int n)
{
    if(n==cnt)
    {
        solve();
        return;
    }
    for(int i=0;i<4;i++)
    {
        v.push_back(i);
        go(n+1);
        v.pop_back();
    }
}
 
int main()
{
    scanf("%d",&t);
    for(int k=1;k<=t;k++)
    {
        scanf("%d",&n);
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<n;j++)
            {
                scanf("%d",&map[i][j]);
                if(map[i][j]==1)
                {
                    if(i==0 || i==n-1 || j==0 || j==n-1) cnt2++;
                    else core.push_back({i,j}),cnt++;
                }
            }
        }
        go(0);
        printf("#%d %d\n",k,SUM);
        core.clear(),cnt=cnt2=CORE=SUM=0;
    }
    return 0;
}