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

1767번 프로세서 연결하기

문제 링크

 

해결방법

DFS + 백트래킹을 통해 모든 경우를 처리하는 완전탐색 문제이다

 

 

⭐️ 솔루션 ⭐️

문제를 처음 보고 완전탐색을 생각했지만 설계가 너무 복잡했다

1. 먼저 가장자리 코어를 제외한 나머지 코어들을 벡터에 넣어준다
2. 4방향을 탐색하여, 전선을 설치할 수 있다면 전선을 설치했다
3. 백트래킹을 활용하여, 전선 설치 - 재귀 - 전선 해체 의 과정을 구현했다

 

문제 조건

• 가장자리에 전원이 공급됨
• 최대한 많은 전원을 연결하고, 최소 전원 길이의 합을 구해야함
• 모든 코어가 반드시 전원에 연결될 필요는 없음
• N≤12 , Core ≤ 12

 

시간복잡도

최대 코어의 개수는 12개이다. 또한 각 코어는 4방향 또는 연결되지 않을 수 있다.

따라서 O(5^12) = 244,140,625 이지만 전선은 겹칠 수 없고, 가장자리 코어는 이미 전원이 공급됐다는 조건때문에 시간초과가 발생하지 않는다

 

 

소스코드

문제 해결 시간 : 1h 40m

메모리 : 12632 KB

시간 : 1683 ms

#include <iostream>
#include <math.h>
#include <cstring>
#include <vector>
#include <algorithm>
#define MAX 12
#define INF 987654321
using namespace std;

struct node {
    int x,y;
    
    node() { }
    node(int _x,int _y) : x(_x),y(_y) { }
};

int testcase;
int n,ans1,ans2;
int map[MAX][MAX];

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

vector<node> core;

void printMap(){
    cout << "\n";
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            cout << map[i][j] << " ";
        }
        cout << "\n";
    }
}

// ans1 = 설치 최대 개수
// ans2 = 전선 최소 개수
// ins = 설치 개수
// sum = 전선 개수
void dfs(int ind,int cnt,int ins,int sum){
    // 모든 코어 작업을 끝낸 경우
    if(cnt == core.size()){
        // 최대의 코어를 설치했을 때, 최소의 전선 개수
        if(ins > ans1){
            ans1 = ins;
            ans2 = sum;
        }else if(ins == ans1){
            ans1 = ins;
            ans2 = min(ans2,sum);
        }
        
        return;
    }
    
    // 설치하는 경우
    for(int i=0; i<4; i++){
        vector<node> tmp;
        
        bool flag = false;
        int nr = core[ind].x;
        int nc = core[ind].y;
        
        while(1){
            if(nr==0 || nc==0 || nr==n-1 || nc==n-1){
                flag = true;
                break;
            }
            
            nr += dx[i];
            nc += dy[i];
            
            if(map[nr][nc] == 0){
                tmp.push_back(node(nr,nc));
            }else{
                break;
            }
        }
        
        if(flag){
            // 전선 설치
            for(int j=0; j<tmp.size(); j++){
                map[tmp[j].x][tmp[j].y] = 2;
            }
            
            dfs(ind+1,cnt+1,ins+1,sum+(int)tmp.size());
            
            // 전선 해체
            for(int j=0; j<tmp.size(); j++){
                map[tmp[j].x][tmp[j].y] = 0;
            }
        }
    }
    
    // 설치하지 않는 경우
    dfs(ind+1,cnt+1,ins,sum);
}

int main(int argc, const char * argv[]) {
    // cin,cout 속도향상
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    cin >> testcase;
    for(int tc=1; tc<=testcase; tc++){
        // 초기화
        core.clear();
        
        cin >> n;
        for(int i=0; i<n; i++){
            for(int j=0; j<n; j++){
                cin >> map[i][j];
                
                if(map[i][j] == 1){
                    // 가장자리 코어들은 제외
                    if(i==0 || j==0 || i==n-1 || j==n-1) continue;
                    
                    core.push_back(node(i,j));
                }
            }
        }
        
        ans1 = 0;
        ans2 = INF;
        dfs(0,0,0,0);
        
        cout << "#" << tc << " " << ans2 << "\n";
    }
    
    return 0;
}