백준 16236번 - 아기상어

백준 16236번 - 아기 상어

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

16236번: 아기 상어

아기 상어 문제는 bfs알고리즘으로 해결하였다.

처음에는 전형적인 bfs문제라 생각하고 문제의 조건 중 가장 가까운 거리에 있는 물고기가 많은 경우의 조건을 잘못

생각해서 bfs를 북 서 동 남 순서대로 돌리면 알아서 조건을 만족할 거라 생각했다.

예제를 돌려보다 이런 방식은 오류가 난다는 것을 알 수 있었다.

vector에 pair로 저장해서 가장 가까운 거리의 물고기를 찾았었는데 정답이 안 나와서

tuple로 바꿔서 tuple(거리, 행, 열) 순으로 저장해 놓은 뒤 sort를 통해 조건을 만족시켰다.

나머지는 일반적인 bfs 문제와 거의 동일하다.

 

#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
#include <tuple>
#include <cstring>
#pragma warning(disable:4996)
using namespace std;
 
int n, x, y;
int baby = 2;
int cnt = 0;
int map[21][21];
int dx[4] = { -1,0,0,1 }; //북,서,동,남
int dy[4] = { 0,-1,1,0 };
bool check[21][21] = { false };
int dis[21][21];
vector<tuple<int,int, int>>v;
 
int count(int a, int b) {
    int ans = 0;
    while (1) {
        memset(check, false, sizeof(check));
        memset(dis, 0, sizeof(dis));
        v.clear();
        queue<pair< int, int >> q;
        q.push(make_pair(a, b));
        check[a][b] = true;
        dis[a][b] = 0;
        int c = 0;
        while (!q.empty()) {
            a = q.front().first;
            b = q.front().second;
            q.pop();
            for (int i = 0; i < 4; i++) {
                int nx = a + dx[i];
                int ny = b + dy[i];
                if (0 <= nx && nx < n && 0 <= ny && ny < n) {
                    if (check[nx][ny] == false && baby >= map[nx][ny]) {
                        q.push(make_pair(nx, ny));
                        check[nx][ny] = true;
                        dis[nx][ny] = dis[a][b] + 1;
                        if (baby > map[nx][ny] && map[nx][ny] != 0) v.push_back(make_tuple(dis[nx][ny], nx, ny));
                    }
                }
            }
        }
        if (!v.empty()) {
            sort(v.begin(), v.end());
            //이동(몇초걸리는지 계산)
            tie(c, a, b) = v.front();
            map[a][b] = 0;
            cnt++;
            if (cnt == baby) {
                cnt = 0;
                baby++;
            }
            ans += dis[a][b];
        }
        else break;
    }
    return ans;
}
 
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            scanf("%d", &map[i][j]);
            if (map[i][j] == 9) {
                x = i;
                y = j; //아기상어의 위치
                map[i][j] = 0;
            }
        }
    }
    printf("%d\n", count(x, y));
}

조건들만 잘 만족시켜주면 쉽게 해결할 수 있다.