[ 백준 16236 ] 아기 상어 (C++)

[문제보기]

 

[해결과정]

 1. input ( n , arr에 맵 입력받기 )

  -> 주의할점! 9는 상어의 초기 위치이다. 상어 위치를 다른 변수에 담고 맵에 9가 아닌 0으로 넣는다.

 

 2. solution 수행

  (1) 현재 상어 위치를 큐에 담는다

  (2) BFS 수행

     -> BFS를 돌며 현재 상어크기보다 같거나 작으면 진입

       -> 만약 현재 상어크기보다 작으면 잡을 수 있는 물고기 ableFish++;

       -> 그리고 map값에 *=-1 하며 음수로 만들기 (음수인 곳은 잡을 수 있는 물고기란 뜻)

       -> minFish에 가장 작은 이동거리 저장시키기

 

  (3) BFS가 끝나면, 맵 처음부터 끝까지 순회

    -> 순회하며 음수인 곳을 가장 처음 만나는 곳이 잡아야 하는 물고기.

    -> 물고기를 잡고, 상어가 잡은 물고기 shsum++;

       -> 만약 shsum 변수가 sh(상어현재크기) 와 같다면 shsum=0, sh++; 하기

 

  (4) 방문 체크배열 초기화, 잡을 수 있는 물고기 변수 ableFish = 0;

 

 

[소스코드]

/*
    BOJ 16236 - 아기 상어
    Created by haejun on 2020/03/11
*/
#include<iostream>
#include<vector>
#include<queue>
#include<memory.h>
#include<math.h>
#include<algorithm>
#include<string>
using namespace std;
const int MAX = 22;
 
int arr[MAX][MAX];
int check[MAX][MAX];
int n;
 
//아기상어 위치
int sy, sx, sh = 2;
//아기상어가 먹은 물고기
int shsum = 0;
 
//좌표 구조체, 큐 생성
struct coor {
    int y;
    int x;
    int cnt;
};
queue <coor> q;
//inside
bool inside(int y, int x) {
    return y >= 0 && y < n && x >= 0 && x < n;
}
int dy[4] = { -1,1,0,0 };
int dx[4] = { 0,0,-1,1 };
 
//이동거리 도합
int maxsum = 0;
 
//잡을 수 있는 물고기 수
//BFS() 돌리고 나서도 0 이라면 끝
int ableFish = 0;
//가장 가까운 물고기
int minFish = 987987987;
 
void bfs() {
    minFish = 987987987;
    while (!q.empty()) {
        int y = q.front().y;
        int x = q.front().x;
        int cnt = q.front().cnt;
        q.pop();
        check[y][x] = cnt;
 
        int ny, nx;
        for (int i = 0; i < 4; i++) {
            ny = y + dy[i];
            nx = x + dx[i];
            if (inside(ny, nx) && check[ny][nx] == 0 && arr[ny][nx] <= sh) {
                if (arr[ny][nx] < sh && arr[ny][nx] != 0) {
                    if (arr[ny][nx] > 0) arr[ny][nx] *= -1;
                    ableFish += 1;
                    if (cnt + 1 < minFish) minFish = cnt + 1;
                }
                check[ny][nx] = cnt + 1;
                q.push({ ny, nx, cnt + 1 });
            }
        }
    }
}
 
void solution() {
    //for문 멈추는 flag;
    int fflag = 0;
    while (true) {
        // 1. 상어 현재 위치 기준으로 BFS 돌리기
        //    먹을 수 있는 고기 파악
        check[sy][sx] = 1;
        q.push({ sy,sx,1 });
        bfs();
        //먹을 수 있는 물고기가 없다면 끝.
        if (ableFish == 0) break;
 
        //가장 가까운 거리의 먹을 수 있는 물고기는 check배열에 minFish 값
        // 2. 먹을 수 있는 물고기
        //    같은 값이라면, 가장 '위' 이면서 가장 '왼쪽' 인 물고기
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (check[i][j] == minFish && arr[i][j] < 0) {
                    //먹은 물고기 
                    shsum += 1;
                    //상어 위치 갱신
                    sy = i; sx = j;
                    //맵에서 물고기 없애기...
                    arr[i][j] = 0;
                    //이동거리 더하기
                    maxsum += minFish - 1;
                    fflag = 1;
                    //만약 먹은 물고기 수와 상어크기가 같다면 상어크기+1
                    if (shsum == sh) {
                        shsum = 0;
                        sh += 1;
                    }
                    break;
                }
            }
            if (fflag == 1) break;
        }
        fflag = 0;
        //잡을 수 있는 물고기 0으로 초기화
        ableFish = 0;
        //방문 배열 초기화
        memset(check, 0, sizeof(check));
    }
}
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
 
    cin >> n;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> arr[i][j];
            if (arr[i][j] == 9) {
                sy = i;
                sx = j;
                arr[i][j] = 0;
            }
        }
    }
 
    solution();
 
    cout << maxsum << endl;
 
    return 0;
}

 

 

[해결 과정 중 실수한 부분 / 잡담]

 5개월 전에 풀었던 문제이다. 그때의 난 누구였는가? 오늘 새로 풀었을 때, 20분 만에 풀이가 완성되었지만.. 아주아주 미세한 실수로 인하여 엄청난 시간을 소요했다. 그 실수는 bfs에 대한 실수였다. 나는 상좌우하 순으로 bfs를 방문하면 자연스레 '가장 위, 가장 왼쪽'을 만족 할 것이라 생각했다. 하지만 가까운 거리라면 그럴 수 있지만, 먼 거리라면... 어느샌가부터 '가장 위, 가장 왼쪽'을 만족하지 못한다. 예를 들자면 큐에 넣은 순서대로 진행이 되니, 어느정도 진행이 됐을 때 왼쪽방향에 있던 큐의 아래 방향을 먼저 탐색하기 시작하여, 우측에 같은 새로줄을 먼저 탐색해야 하는 규칙에 어긋나게 된다.

 

 이것은 어떻게 보면 미세한 실수지만, 굉장히 큰 실수다. BFS에 대한 이해도가 높았다고 자만했던 나인데,, 반성한다.

 

[관련 문제 혹은 비슷한 문제]

 삼성 역량테스트