1767.프로세서 연결하기

이번에 풀어볼 문제는 SW Expert의 샘플 문제 1767번 프로세서 연결하기이다.

굉장히 재미있는 문제였던거 같다. 물론 한 번에 못풀었다..

처음 도전했을 때는 끝에가서 설계를 잘못했다는 걸 깨달았고 다음날 다시 처음부터 풀었다.

항상 말하지만 충분한 생각과 설계가 중요하다. 두 번째 다시 도전했을 때 충분한 생각과 설계 후 한 번에 맞았다.

=> 한 번에 맞았다는 것과 나의 설계가 맞아서 그런지 기분이 좋다ㅎㅎ

SW Expert Academy

 

---

나의 설계는 다음과 같다.

1. 벽면에 붙어 있는 Core들은 바로 전원이 연결되기 때문에 탐색에서 제외한다.

2. 나머지 Core들을 탐색하되 가장 짧게 전선을 연결할 수 있는 방향을 구한 뒤, 그 방향으로 전선을 연결한다.

3. Core 탐색 순서를 바꿔가면서 최단 전선을 구한다.

4. 가장 많은 Core의 전원이 연결된 경우일 때 전선의 최소 길이를 구한다.

=> 설명이 어려울 수 있으니 대충 그림으로 그려보았다.

 

 

이런식으로 우리가 탐색하는 Core를 순서대로 전선길이가 최소일 때의 경우를 구한다. 

모든 Core의 탐색이 끝나면 제일 먼저 탐색했던 좌표를 제일 뒤로 보내고

다시 최소 전선길이의 탐색을 시작한다. 각각의 좌표쌍이 한 번씩 첫 번째 순서로 탐색이 진행되면 끝이난다.

 

 

 

 

이런식으로 계속 탐색을 진행하면 최소 전선의 경우의 수들을 구할 수 있게 된다. 

단, 주의할 점은 전선의 최소길이가 중요한게 아니라

최대한 많은 Core에 전원을 연결한 상태에서의 전선의 최소값을 구해야한다.

---

< Code 설명 >

#pragma warning(disable:4996)
#include <iostream>
#include <deque>
#include <string.h>
#include <algorithm>
 
#define MAX 13
 
using namespace std;
 
int map[MAX][MAX];
int check[MAX][MAX]; // 연결된 전선의 형태가 저장됨
 
int T, N;
 
int dx[4] = { 0, -1, 0, 1 }; // 서 북 동 남
int dy[4] = { -1, 0, 1, 0 };
 
 
deque<pair<int,int>> core; // 탐색 core좌표 저장 deque
int min_len = 987654321;
int short_dir = -1;
int cnt = 0; // 전원이 연결된 core의 갯수
 
void reset(){ // 다음 테스트 케이스를 위한 초기화
    core.clear();
    min_len = 987654321;
    short_dir = -1;
    memset(check, 0, sizeof(check));
    memset(map, 0, sizeof(map));
}
 
void change(){ // 첫 탐색의 core의 좌표를 바꿔줌
    core.push_back(core.front());
    core.pop_front();
}
 
void search(int x, int y, int t){ // 가장짧은 전선의 방향 구하기
    int ax = x + dx[t];
    int ay = y + dy[t];
    if (x < 0 || y < 0 || x >= N || y >= N){ // 전선이 벽에 닿았을때
        if (check[x][y] < min_len){ // 그중 전선의 길이가 가장짧을때
            min_len = check[x][y]; // 해당 전선의 길이를 저장하고
            short_dir = t; // 해당 방향도 저장
        }
        return;
    }
    if (!check[ax][ay] && map[ax][ay] != 1){ // 전선을 놓을 수 있다면
        check[ax][ay] = check[x][y] + 1; // 점점 벽쪽으로 전선이 나아감
        search(ax, ay, t); // 나아간 좌표로 또 탐색
        check[ax][ay] = 0; // 해당 방향 탐색 후에는 다른 방향을 탐색하기 위해 0으로 초기화
    }
    else if (check[ax][ay] || map[ax][ay] == 1) // 탐색중간에 core나 전선이 있는 경우
        return;
 
}
 
void go(int x, int y, int dir){ // 최소의 전선 길이의 방향으로 전선 연결하는 함수
    for (int i = 0; i < N; i++){
        int ax = x + dx[dir];
        int ay = y + dy[dir];
        if (ax < 0 || ay < 0 || ax >= N || ay >= N){
            cnt += 1; // 전선이 연결되면 전원이 연결된 core의 갯수 +1
            break;
        }
        check[ax][ay] = true; // 전선이 점점 벽쪽으로 향함
        x = ax;
        y = ay;
    }
}
 
int check_line(){ // 연결된 전선의 길이 파악
    int line = 0;
    for (int i = 0; i < N; i++){
        for (int j = 0; j < N; j++){
            if (check[i][j] == 1)
                line += 1;
        }
    }
    return line;
}
int main() {
    freopen("1767.txt", "r", stdin);
    cin >> T;
    for (int z = 1; z <= T; z++){
        reset();
 
        cin >> N;
        for (int i = 0; i < N; i++){
            for (int j = 0; j < N; j++){
                cin >> map[i][j];
                if ((i == 0 || i == N || j == 0 || j == N) && map[i][j] == 1) // 벽에 붙은 core들은 pass
                    continue;
                
                if (map[i][j] == 1) // 벽에 붙어있지 않는 core들만 탐색
                    core.push_back(make_pair(i, j));
             }
        }
        int size = core.size(); // 탐색할 core 좌표쌍의 갯수
        int x, y; // 탐색 시작 좌표 변수
        int core_max = -1;      // 가장많은 core연결 변수 초기화
        int answer = 987654321; // 정답 초기화
        for (int w = 0; w < size; w++){ // 탐색 시작 core 바꿔가며 탐색
            for (int i = 0; i < size; i++){ // 다음 core 검색
                for (int j = 0; j < 4; j++){ // 4방향중 가장 짧은 방향 탐색
                    x = core[i].first; // 탐색할 core 좌표사용
                    y = core[i].second;
                    search(x, y, j); // 가장 짧은 전선 방향 탐색, j를 이용해서 4방향을 탐색함
                }
                if (short_dir!=-1) // core가 전선과 연결되는 경우
                    go(x, y, short_dir); // 가장 짧은 전선으로 core 연결
                short_dir = -1; //가장 짧은 전선 방향 초기화
                min_len = 987654321; //가장 짧은 전선 길이 초기화
            }
            //core가 최대일 때 전선의 최소값만 구하는 함수
            if (cnt >= core_max){ // 가장 core가 많이 연결되었을 때
                core_max = cnt;
                answer = check_line();// 라인수를 센다.
                if (cnt == core_max) // 연결된 core수가 같을 때는
                    answer = min(answer, check_line()); // 가장 적은 전선의 수가 정답
            }
            cnt = 0; // 연결된 core수 초기화
            change(); // 첫 탐색의 core 순서 변경
            memset(check, 0, sizeof(check)); // 전선 배열 초기화
        }
 
        cout << "#" << z << " " << answer << endl;
    }
    return 0;
}

# 결국은 항상 똑같다. 설계를 잘하고 예외를 생각해주어야 문제를 풀 수 있다. 

  구현은 그 다음 문제다!