[boj] 백준 16236 아기 상어 - BFS

[문제]

https://www.acmicpc.net/problem/16236

16236번: 아기 상어

 

[풀이]

일단 조건이 많아서 복잡해 보이는데,,,흐름을 정리하자면 다음과 같다.

1. 아기 상어가 처음 위치한 곳에서 BFS를 돌린다. 아기 상어가 먹을 수 있는 물고기가 더이상 없을 때까지 반복하며 먹을 수 있는 물고기의 거리, 위치를 eat_fish vector에 저장한다.

2. BFS가 끝나면 아기 상어가 먹으러 갈 물고기를 찾는다.

 1) 가장 가까운 곳에 위치한 물고기

 2) 가장 위에 있는 물고기 (=y좌표가 작은 순서)

 3) 가장 왼쪽에 있는 물고기 (=x좌표가 작은 순서)

 조건은 다음과 같다. 애초에 eat_fish vector를  { 거리, { y좌표, x좌표} } 로 저장했으므로 sort를 하면 조건에 맞게 정렬된다. 

3. 아기 상어가 잡아 먹은 물고기의 위치를 통해 몇 초 이동했는지 정답을 갱신하고, 그 위치에서 다시 BFS를 시작한다. 아기 상어가 해당 위치에 있는 물고기를 잡아 먹었으므로 map[r][c] 는 0으로 바꿔준다.

4. 아기 상어가 잡아 먹은 물고기의 count를 증가시켜준다. 만약 count가 아기 상어 크기와 같아지면, 아기 상어 크기를 증가시키고 count는 다시 0으로 초기화한다.

 

추가로 BFS 돌릴 때마다 eat_fish vector랑 check 배열 초기화 해주기! 

 

 

[코드]

 

#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
#include <queue>

using namespace::std;

int n;
int map[21][21];
int check[21][21];
int dx[] = {0, 0, -1, 1};
int dy[] = {1, -1, 0, 0};
vector<pair<int, pair<int, int>>> eat_fish;
int r, c;
int bs = 2;

void bfs(int y, int x, int bs){ //bs 아기 상어 크기
    memset(check, -1, sizeof(check));
    eat_fish.clear();
    queue<pair<int,int>> q;
    q.push({y,x});
    check[y][x] = 0;

    while(!q.empty()){
        y = q.front().first;
        x = q.front().second;
        q.pop();

        for(int i=0; i<4; i++){
            int nr = y + dy[i];
            int nc = x + dx[i];

            if(nr < 0 || nr >= n || nc < 0 || nc >= n || check[nr][nc]!=-1 || map[nr][nc] > bs) continue;

            if(map[nr][nc]==0 || map[nr][nc]==bs){ //지나갈 수 있음
                check[nr][nc] = check[y][x] + 1; //아기 상어로부터 얼마나 멀리 떨어졌는지 기록
                q.push({nr, nc});
            }

            if(map[nr][nc]<bs && map[nr][nc]>=1){ //잡아 먹고, 지나갈 수 있음
                check[nr][nc] = check[y][x] + 1;
                eat_fish.push_back( {check[nr][nc],{nr, nc}});
                q.push({nr, nc});
            }
        }
    }


}

int main() {

    int count = 0, answer=0;

    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){
                map[i][j] = 0; //크기를 9로 인식해서 아기상어가 해당 위치를 못지나갈 수 있으므로 0으로 초기화
                r = i;
                c = j;
            }
        }
    }

    while(true){

        bfs(r, c, bs);

        if(eat_fish.empty())
            break;

        //1. 가장 가까운 2. 가장 위에 있는(y좌표가 작은) 3. 가장 왼쪽에 있는(x좌표가 작은)
        sort(eat_fish.begin(), eat_fish.end());
        count++; // 아기 상어가 먹은 물고기 수
        answer += eat_fish[0].first; //아기 상어가 물고기를 먹으러 몇 초 이동했는지
        r = eat_fish[0].second.first;
        c = eat_fish[0].second.second; //아기 상어 위치 갱신
        map[r][c] = 0; //아기상어가 잡아먹어서 0이 됨

        if(bs == count){
            bs++; //아기 상어 크기 증가
            count = 0;
        }
    }

    cout << answer;
}