ABOUT ME

-

Today
-
Yesterday
-
Total
-
  • 1767.프로세서 연결하기
    알고리즘/SW Expert Academy 2020. 6. 16. 23:37

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

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

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

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

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

     

    SW Expert Academy

    SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!

    swexpertacademy.com

     


    나의 설계는 다음과 같다.

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

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

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

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

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

     

     

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

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

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

     

     

     

     

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

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

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


    < Code 설명 >

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    89
    90
    91
    92
    93
    94
    95
    96
    97
    98
    99
    100
    101
    102
    103
    104
    105
    106
    107
    108
    109
    110
    111
    112
    113
    114
    115
    116
    117
    118
    119
    120
    121
    122
    123
    124
    125
    126
    127
    128
    129
    130
    131
    #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-101 }; // 서 북 동 남
    int dy[4= { -1010 };
     
     
    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, 0sizeof(check));
        memset(map, 0sizeof(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, 0sizeof(check)); // 전선 배열 초기화
            }
     
            cout << "#" << z << " " << answer << endl;
        }
        return 0;
    }
    cs

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

      구현은 그 다음 문제다!

     

     

    '알고리즘 > SW Expert Academy' 카테고리의 다른 글

    4008.숫자 만들기  (0) 2020.06.19
    5658.보물상자 비밀번호  (0) 2020.06.18
    1767.프로세서 연결하기  (0) 2020.06.16
    5650.핀볼 게임  (0) 2020.06.14
    5656.벽돌깨기  (0) 2020.06.12
    2117.홈 방범 서비스  (0) 2020.06.06

    댓글 0

Designed by Tistory.