ABOUT ME

-

Today
-
Yesterday
-
Total
-
  • 5650.핀볼 게임
    알고리즘/SW Expert Academy 2020. 6. 14. 13:40

    이번에 풀어볼 문제는 핀볼게임이다. 정답률은 31%정도인데 나의 체감은 60%정도가 맞지 않나싶다.

    오히려 5656번 벽돌깨기가 체감난이도가 더 높았다. 근데 그건.. 정답률이 60%... 여튼 한 번에 풀어서 다행이다.

    톱니봐퀴나 핀볼게임이나 공통점은 문제를 풀면서 딱히 큰 예외를 신경쓰지 않아도 될 것같다는 느낌과

    정확하게만 구현하면 딱히 큰 예외가 없어서 한 번에 정답이 맞겠다는 느낌이 오는 문제였다는 것이다.

    내 코드가 좋다는 것은 아니지만 그냥 하라는대로 하니까 풀린 문제이다.

     

    SW Expert Academy

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

    swexpertacademy.com


     

    설명은 딱히 없다. 풀이 방식은 다음과 같다.

    1. 빈 칸에 핀볼이 떨어져서 상, 하, 좌, 우로 움직인다 => 즉, 빈칸에 다 들어가고 4방향으로 탐색하는 경우의 수를 다해봐야한다.

    2. 그 다음 부터는 그냥 벽돌모양과 벽에 부딪히는 것에 대해 똑같이 구현만 해주면 된다.

    그래서 나는 현재 방향을 변수로 처리해서 방향이 바뀔 때마다 해당 변수 값만 바꿔주면서 문제를 풀었다..

    웜홀의 경우는 deque로 짝을 지어줘서 2개가 1쌍이므로 현재 좌표와 다른 웜홀 좌표를 사용했다.

     


    < 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
    132
    133
    134
    135
    136
    137
    138
    139
    140
    141
    142
    143
    144
    145
    146
    147
    148
    149
    150
    151
    152
    153
    154
    155
    156
    157
    158
    159
    160
    161
    162
    163
    164
    165
    166
    167
    168
    169
    170
    171
    172
    173
    174
    175
    176
    177
    178
    179
    180
    181
    182
    183
    184
    185
    186
    187
    188
    189
    190
    191
    192
    193
    194
    195
    196
    197
    198
    199
    200
    201
    202
    203
    204
    205
    206
    207
    208
    209
    210
    211
    212
    213
    214
    215
    216
    217
    218
    219
    220
    221
    222
    223
    224
    225
    226
    227
    228
    229
    230
    231
    232
    233
    234
    235
    236
    237
    238
    239
    240
    241
    242
    243
    244
    #pragma warning(disable:4996)
    #include <iostream>
    #include <deque>
    #include <algorithm>
    #include <string.h>
     
    #define MAX 101 
    using namespace std;
     
    int T, N;
    int map[MAX][MAX];
     
    int dx[4= { 0-101 }; // 좌, 상, 우 하
    int dy[4= { -1010 };
     
    deque<int>x_mov;
    deque<int>y_mov;
     
    deque<pair<intint>>hole1;
    deque<pair<intint>>hole2;
    deque<pair<intint>>hole3;
    deque<pair<intint>>hole4;
    deque<pair<intint>>hole5;
     
     
    void dir_set(){ // 방향 deque 저장
        for (int i = 0; i < 4; i++){
            x_mov.push_back(dx[i]);
            y_mov.push_back(dy[i]);
        }
    }
     
    void dir_modi(){ // 시작 방향 변경 함수(상하좌우 4방향)
        x_mov.push_back(x_mov.front());
        x_mov.pop_front();
        y_mov.push_back(x_mov.front());
        y_mov.pop_front();
    }
     
    bool crash_wall(int x, int y){
        if (x < 0 || y < 0 || x >= N || y >= N) // 맵 벽에 부딪히는 경우
            return true;
        return false;
    }
     
    void hole_change(int num){ // 자기 짝에 맞는 웜홀로 움직이게하는 함수
        switch (num)
        {
        case 6:
            hole1.push_back(hole1.front());
            hole1.pop_front();
            break;
        case 7:
            hole2.push_back(hole2.front());
            hole2.pop_front();
            break;
        case 8:
            hole3.push_back(hole3.front());
            hole3.pop_front();
            break;
        case 9:
            hole4.push_back(hole4.front());
            hole4.pop_front();
            break;
        case 10:
            hole5.push_back(hole5.front());
            hole5.pop_front();
            break;
        }
    }
     
    int play(int x, int y){
        int num = 0;
        int first_x = x;
        int first_y = y;
        int max_point = 0;
        for (int t = 0; t < 4; t++){ //4방향 탐색을 위한 반복문
            int point = 0;
            int cur_tmp_x = x_mov[t];
            int cur_tmp_y = y_mov[t];
            x = first_x;
            y = first_y;
            while (true){ //방향 하나당 끝날때까지 진행
                int ax = x + cur_tmp_x; // 해당 방향으로 전진
                int ay = y + cur_tmp_y; // 해당 방향으로 전진
                if ((ax == first_x && ay == first_y) || map[ax][ay] == -1){
                    // 시작점을 돌아오거나 블랙홀을 만나면 종료
                    if (point > max_point) // 최대 포인트 저장
                        max_point = point;
                    break;
                }
                if (crash_wall(ax,ay) || map[ax][ay] == 5// 맵 벽에 부딪히는 경우, 5번에 부딪히거나
                {
                    // 부딪힌 방향의 반대로 감
                    if (cur_tmp_x == 1 && cur_tmp_y == 0)
                        cur_tmp_x = -1;
                    else if (cur_tmp_x == -1 && cur_tmp_y == 0)
                        cur_tmp_x = 1;
                    else if (cur_tmp_x == 0 && cur_tmp_y == 1)
                        cur_tmp_y = -1;
                    else if (cur_tmp_x == 0 && cur_tmp_y == -1)
                        cur_tmp_y = 1;
                    point += 1// 벽에 부딪혔으니 포인트 +1;
                }
     
                // 웜홀에 들어가는 경우
                else if (map[ax][ay]>5){
                    if (map[ax][ay] == 6){
                        if (ax == hole1.front().first && ay == hole1.front().second)
                            hole_change(6);
                        ax = hole1.front().first;
                        ay = hole1.front().second;
                    }
                    else if (map[ax][ay] == 7){
                        if (ax == hole2.front().first && ay == hole2.front().second)
                            hole_change(7);
                        ax = hole2.front().first;
                        ay = hole2.front().second;
                    }
                    else if (map[ax][ay] == 8){
                        if (ax == hole3.front().first && ay == hole3.front().second)
                            hole_change(8);
                        ax = hole3.front().first;
                        ay = hole3.front().second;
                    }
                    else if (map[ax][ay] == 9){
                        if (ax == hole4.front().first && ay == hole4.front().second)
                            hole_change(9);
                        ax = hole4.front().first;
                        ay = hole4.front().second;
                    }
                    else if (map[ax][ay] == 10){
                        if (ax == hole5.front().first && ay == hole5.front().second)
                            hole_change(10);
                        ax = hole5.front().first;
                        ay = hole5.front().second;
                    }
                }
     
                // 세모 모양 중 평면에 부딪히는 경우 
                else if ((map[ax][ay] == 1 || map[ax][ay] == 2&& (cur_tmp_x == 0 && cur_tmp_y == 1)){
                    cur_tmp_x = 0;
                    cur_tmp_y = -1;
                    // 0, -1
                    point += 1// 벽에 부딪혔으니 포인트 +1;
                }
                else if ((map[ax][ay] == 1 || map[ax][ay] == 4&& (cur_tmp_x == -1 && cur_tmp_y == 0)){
                    cur_tmp_x = 1;
                    cur_tmp_y = 0;
                    // 1, 0
                    point += 1// 벽에 부딪혔으니 포인트 +1;
                }
                else if ((map[ax][ay] == 2 || map[ax][ay] == 3&& (cur_tmp_x == 1 && cur_tmp_y == 0)){
                    cur_tmp_x = -1;
                    cur_tmp_y = 0;
                    // -1, 0
                    point += 1// 벽에 부딪혔으니 포인트 +1;
                }
                else if ((map[ax][ay] == 3 || map[ax][ay] == 4&& (cur_tmp_x == 0 && cur_tmp_y == -1)){
                    cur_tmp_x = 0;
                    cur_tmp_y = 1;
                    // 0, 1
                    point += 1// 벽에 부딪혔으니 포인트 +1;
                }
     
     
                // 세모모양 중 대각벽에 부딪히는 경우
                else if ((map[ax][ay] == 1 || map[ax][ay] == 2&& (cur_tmp_x == 1 || cur_tmp_x == -1&& cur_tmp_y == 0){ // 상, 하 => 우
                    cur_tmp_x = 0;
                    cur_tmp_y = 1;
                    // 0, 1
                    point += 1// 벽에 부딪혔으니 포인트 +1;
                }
                else if ((map[ax][ay] == 1 || map[ax][ay] == 4&& cur_tmp_x == 0 && (cur_tmp_y == -1 || cur_tmp_y == 1)){ // 좌, 우 => 상
                    cur_tmp_x = -1;
                    cur_tmp_y = 0;
                    // -1, 0
                    point += 1// 벽에 부딪혔으니 포인트 +1;
     
                }
                else if ((map[ax][ay] == 2 || map[ax][ay] == 3&& cur_tmp_x == 0 && (cur_tmp_y == -1 || cur_tmp_y == 1)){ // 좌, 우 => 하
                    cur_tmp_x = 1;
                    cur_tmp_y = 0;
                    //1, 0
                    point += 1// 벽에 부딪혔으니 포인트 +1;
     
                }
                else if ((map[ax][ay] == 3 || map[ax][ay] == 4&& (cur_tmp_x == 1 || cur_tmp_x == -1&& cur_tmp_y == 0){// 상, 하 => 좌
                    cur_tmp_x = 0;
                    cur_tmp_y = -1;
                    // 0, -1
                    point += 1// 벽에 부딪혔으니 포인트 +1;
                }
                x = ax, y = ay;
            }
        }
        return max_point;
    }
     
    void reset(){
        memset(map, 0sizeof(map));
        x_mov.clear();
        y_mov.clear();
        hole1.clear();
        hole2.clear();
        hole3.clear();
        hole4.clear();
        hole5.clear();
    }
    int main() {
        freopen("5650.txt""r", stdin);
        cin >> T;
        for (int z = 1; z <= T; z++){
            reset();
            deque<pair<intint>>start;
            cin >> N;
            for (int i = 0; i < N; i++){
                for (int j = 0; j < N; j++){
                    cin >> map[i][j];
                    if (map[i][j]==0)
                        start.push_back(make_pair(i, j));
                    else if (map[i][j] == 6)
                        hole1.push_back(make_pair(i, j));
                    else if (map[i][j] == 7)
                        hole2.push_back(make_pair(i, j));
                    else if (map[i][j] == 8)
                        hole3.push_back(make_pair(i, j));
                    else if (map[i][j] == 9)
                        hole4.push_back(make_pair(i, j));
                    else if (map[i][j] == 10)
                        hole5.push_back(make_pair(i, j));
                }
            }
            int start_pos = start.size(); // 공을 놓을 수 있는 위치
            dir_set();
            int answer = -777;
            for (int i = 0; i < start_pos; i++){
                answer = max(answer,play(start.front().first, start.front().second));
                start.pop_front();
            }
            cout << "#" << z << " " << answer << "\n";
        }
        return 0;
    }
    cs

    # 무식하게 푼 것 같지만... 풀긴 풀었으니까.. 조금 더 보완하면 되지 않을까??

      코드는 보다시피 줄일 수 있다. 보완할 점은 줄일 수 있는 코드를 줄이면서 코드를 짤 수 있는 설계능력인 것 같다..

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

    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
    5653.줄기세포배양  (0) 2020.06.06

    댓글 0

Designed by Tistory.