ABOUT ME

-

Today
-
Yesterday
-
Total
-
  • 16236.아기상어
    알고리즘/백준 BAEK JOON 2020. 5. 31. 15:06

    이번에 풀어볼 문제는 백준 16236의 아기상어이다. 시뮬레이션 + 탐색의 문제이며 요즘 점점 설계의 중요성을 깨닫는다.

    이 문제를 잘 풀기 위해서는 자신이 구하고자하는 내용들의 순서로직의 설계를 잘해주어야 한다.

    아직 설계능력이 많이 미숙한 것 같다. 하다보면 늘겠지..

     

    16236번: 아기 상어

    N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가��

    www.acmicpc.net

     

     


    < 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

    #pragma
     warning(disable:4996)
    #include <iostream>
    #include <queue>
    #include <string.h>
     
    #define MAX 21
    #define BOOL_CMP 777 //비교대상의 될 임의의 값
     
    using namespace std;
     
    int map[MAX][MAX];   // 맵이 저장되는 공간
    int check[MAX][MAX]; // 걸린 시간이 저장되는 공간
     
    int dx[4= { 00-11 };
    int dy[4= { -1100 };
    int n, src_x, src_y, tmp_x, tmp_y, help_cmp;
     
    int shark = 2// 상어의 크기
    queue <pair<intint>>spot; // 좌표저장될 큐
     
     
    void showme(){ // 현재 배열내용 보여주기
        cout << "\n";
        for (int i = 0; i < n; i++){
            for (int j = 0; j < n; j++){
                cout << map[i][j] << " ";
            }
            cout << "\n";
        }
        cout << "\n";
        cout << "\n";
        for (int i = 0; i < n; i++){
            for (int j = 0; j < n; j++){
                cout << check[i][j] << " ";
            }
            cout << "\n";
        }
        cout << "\n";
    }
    void reset(){ // 초기화
        help_cmp =tmp_x = tmp_y = BOOL_CMP;// 비교대상과 임시좌표 초기화
        memset(check, 0sizeof(check)); // check 배열 초기화
    }
    void queue_clear(){ // 큐 초기화
        int size = spot.size();
        for (int i = 0; i < size; i++)
            spot.pop();
    }
    void search(int x, int y){ //탐색(BFS)
        while (!spot.empty()){
            x = spot.front().first; x좌표 사용
            y = spot.front().second; y좌표 사용
            spot.pop(); // 사용했으니 버린다
            //showme();
            for (int i = 0; i < 4; i++){
                int ax = x + dx[i]; // 좌표기준 상하좌우 탐색
                int ay = y + dy[i]; // 좌표기준 상하좌우 탐색
                if (ax < 0 || ay < 0 || ax >= n || ay >= n)
                    continue;  // 맵 범위를 벗어나면 넘어감
                    
                // 먹을수도 있고 지나갈 수도 있는 경우
                if (!check[ax][ay] && map[ax][ay] <= shark){ 
                     // 이동 했으므로 시간 증가
                    check[ax][ay] = check[x][y] + 1
                    spot.push(make_pair(ax, ay));//해당 좌표 저장
                    
                    // 먹을 수 있는 먹이가 있다면
                    if (map[ax][ay]!= 0 && map[ax][ay] < shark){ 
                        // 먹을 수 있는 첫 번째 먹이체크
                        if (help_cmp > check[ax][ay]){ 
                            // 해당 크기 기록해놓음
                            help_cmp = check[ax][ay]; 
                            tmp_x = ax; // 해당 x좌표 기록
                            tmp_y = ay; // 해당 y좌표 기록
                        }
                        
                         // 먹을 수 있는 먹이가 여러개인 경우
                        else if (help_cmp == check[ax][ay]){
                            // x축의 크기가 같다면 위쪽이 먼저
                            if (tmp_x == ax){   
                                // y값이 작을 수록 위쪽이므로
                                if (tmp_y > ay) 
                                     //작은값 저장
                                    tmp_y = ay;
                            }
                            
                            // x축은 왼쪽이 우선이다.
                            else if (tmp_x > ax){
                                tmp_x = ax;
                                tmp_y = ay;
                            }
                        }
                    }
                }
            }
        }
    }
     
     
    int main() {
        //freopen("16236.txt", "r", stdin);
        cin >> n;
        for (int i = 0; i < n; i++){
            for (int j = 0; j < n; j++){
                cin >> map[i][j];
                if (map[i][j] == 9){
                    spot.push(make_pair(i, j));
                    map[i][j] = 0//큐에 넣었으니 0으로 초기화
                }
            }
        }
     
        int ans = 0// 총 걸린시간
        int cnt = 0// 먹은 먹이량
        while (true){
            reset(); // 초기화 
            src_x = spot.front().first; // 시작 x좌표 사용
            src_y = spot.front().second;// 시작 y좌표 사용
            search(src_x, src_y); // 탐색시작
            
            // 임의의 비교값이 변경되었다면 탐색내의 로직상 먹이를 발견했다는 의미
            if (tmp_x != BOOL_CMP && tmp_y != BOOL_CMP){
                cnt += 1// 먹은 먹이수 +1
                ans += check[tmp_x][tmp_y]; // 해당 시간값 누산
                map[tmp_x][tmp_y] = 0// 먹은 물고기 0으로 초기화
                if (cnt == shark){// 상어크기만큼 먹었다면
                    shark += 1// 상어크기 +1
                    cnt = 0;    // 다시 카운트해야하므로 0
                }
                queue_clear(); // 큐를 비워주고
                
                //먹은 부분부터 시작하기위해 좌표저장
                spot.push(make_pair(tmp_x, tmp_y));
            }
            else // 먹을게 없다면 종료
                break;
        }
        cout << ans << "\n";
        return 0;
    }
    cs
    반응형

    '알고리즘 > 백준 BAEK JOON' 카테고리의 다른 글

    15686.치킨배달  (0) 2020.08.11
    14503.로봇청소기  (0) 2020.06.01
    14890.경사로  (0) 2020.05.28
    1697.숨바꼭질  (0) 2020.05.27
    2468.안전영역  (0) 2020.05.26

    댓글

Designed by Tistory.