16236.아기상어

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

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

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

16236번: 아기 상어

 

 

---

< Code 설명 >

#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] = { 0, 0, -1, 1 };
int dy[4] = { -1, 1, 0, 0 };
int n, src_x, src_y, tmp_x, tmp_y, help_cmp;
 
int shark = 2; // 상어의 크기
queue <pair<int, int>>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, 0, sizeof(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;
}