[백준] 16236 - 아기 상어

이 문제를 풀면서 거의 두 시간정도 아기상어 노래를 부른거 같닼ㅋㅋㅋㅋㅋㅋㅋㅋㅋ

문제를 이해하고 구현하는데 1시간 걸렸는데....

풀고보니 내가 이해한건 90퍼 였다

나머지 10퍼는 디버깅하면서 찾느라 30분 정도 걸림....

자 문제의 조건에 대해서 생각하며 BFS탐색과 메모이제이션?이라고 해야하나...만족하는 값을 저장하고 갱신하는 방법으로 진행했다.

1. BFS탐색을 통해 최단거리 내의(맨위, 맨 왼쪽->문제의 조건을 만족하는 지점)의 갈 수 있는 곳을 찾는다.

2. 찾았다면 갈 수 있는 지점이라 판단, list에 저장한다.

3. 계속 BFS 탐색이 종료되면 문제의 조건에 맞게 sort한다.

4. 저장된 list[0].dis를 리턴함으로서 거리를 더해 주고, 그 위치를 map에서 삭제한다.

5. 먹은 물고기 갯수가 아기 상어의 크기와 같아지면 크기를 더해주고, 먹은 갯수를 0으로 만들어 준다.

6. 이 과정을 BFS함수가 리턴되는 값이 0이 되면 멈추고 답을 출력한다.

두 시간동안 삽질한 문제지만 애귀상어 노래를 부르며 즐겁게 풀 수 있었다 ㅎㅎ

#include <iostream>
#include <cmath>
#include <algorithm>
#define MX 22
using namespace std;
 
struct QUEUE {
    int x, y, dis;
}q[MX*MX];
 
struct SHARK {
    int x, y, k, ate;
}shark;
 
bool com(const QUEUE i, const QUEUE j)
{
    return (i.dis < j.dis) || (i.dis == j.dis && i.y < j.y) || (i.dis == j.dis && i.y == j.y && i.x < j.x);
}
 
int map[MX][MX], numcheck[MX][MX];
int dx[] = { 0, -1, 1, 0 };
int dy[] = { -1, 0, 0, 1 };
int N, M, dab, nx, ny;
 
int bfs()
{
    int st, ed, ix, iy, point, check[MX][MX] = { 0 };
    QUEUE list[MX*MX] = { 0 };
    st = ed = point = -1;
    q[++st].x = shark.x; q[st].y = shark.y; check[shark.y][shark.x] = 1;
 
    while (st != ed)
    {
        ix = q[++ed].x; iy = q[ed].y;
        if (0 < map[iy][ix] && map[iy][ix] < shark.k) { list[++point].x = ix; list[point].y = iy; list[point].dis = check[iy][ix] - 1; }
        for (int i = 0; i < 4; i++)
        {
            nx = ix + dx[i]; ny = iy + dy[i];
            if (nx < 0 || ny < 0 || nx >= N || ny >= N || check[ny][nx] || map[ny][nx] > shark.k) continue;
            q[++st].x = nx; q[st].y = ny; check[ny][nx] = check[iy][ix] + 1;
        }
    }
    sort(list, list + (point + 1), com);
    shark.x = list[0].x; shark.y = list[0].y;
    return list[0].dis;
}
 
int main(void)
{
    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) { shark.k = 2; shark.x = j; shark.y = i; map[i][j] = 0; }
        }
    while (true)
    {
        int dis = bfs();
        if (!dis) break;
        else shark.ate++;
        if (shark.k == shark.ate) { shark.k++; shark.ate = 0; }
        dab += dis;
        map[shark.y][shark.x] = 0;
    }
    cout << dab << endl;
    return 0;
}