백준 16236번 아기 상어 C++ BFS

리뷰

조건에 쉬워보였으나 굉장히 까다로웠던 문제, bfs함수 내에서 2중 while문과 sort를 통해 풀었다.

 

문제 풀이

1. 2차 배열 필드를 입력받고 만약 현재 입력값이 9라면 아기 상어 이므로 좌표를 저장해 준다.
2. bfs를 시작하고 total_time을 0으로 초기화 한 후 while문을 항상 true인 상태로 개행해 준다.
3. 이후 일반적인 bfs와 동일하게 큐와 방문 배열(여기선 거리계산 역할까지 병행)을 초기화 하고 큐에 시작 위치를 담은 pos 구조체를 추가해 준 뒤 현재 위치의 거리를 0으로 초기화 해준다.
4. 잡아먹은 물고기 정보를 저장할 fishes 벡터를 초기화 해주고 최소 거리를 -1로 잡은 후 bfs를 실행해 준다.
5. 4방향 탐색을 하고 만약 거리가 -1(방문하지 않은)이면서 2차 배열의 값이 아기 상어의 몸집보다 크거나 작으면 해당 좌표를 방문하고 현재 거리에서 + 1을 한 값으로 방문 배열에 저장해 주고, 큐에 푸시를 해준다.
6. 만약 해당 위치에 잡아먹을 수 있는 물고기가 있고, 아직 아무 물고기도 잡아 먹지 않은 상태거나 이전에 잡아먹었던 물고기 보다 가까이 있을 경우 현재 위치까지의 거리를 최소 거리로 갱신해 준 뒤 fishes 벡터 초기화 및 새로운 좌표와 거리, 현재 몸집과 먹은 횟수를 fishes 벡터에 저장해 준다.
7. 만약 현재 거리와 여태까지의 최소 거리가 동일할 경우 fishes 벡터에 저장해 준다.
8. while문이 종료된 후 fishes 벡터가 비어있다면 더 이상 먹을 물고기가 없는 것이므로 total_time을 리턴해 준다.
9. fishes 벡터가 비어있지 않다면 먹은 물고기를 x가 적은 순, y가 적은순으로 정렬해 준다.
10. 정렬 후 첫번째 물고기가 가장 위쪽이면서 왼쪽인 물고기 이므로 해당 물고기의 거리만큼 total_time에 더해준다.
11. 다시 start 큐에 해당 물고기 정보를 추가해 준다. 이때 eat을 + 1 해주고 현재 몸집과 같다면 eat을 0으로, 몸집을 1만큼 키워준다. 이후 잡아먹은 물고기는 2차 배열에서 0으로 변경해 준다.

 

참고 사항

방향 배열만으로 문제에서 요구하는 조건을 만족할 수 없다.

BFS로 물고기를 잡아먹는 모든 경우의 수를 찾은 뒤, 좌표 값이 가장 위쪽이면서 왼쪽인 물고기를 찾아야 한다.

2중 while문을 사용하면 시간복잡도가 굉장히 높아질줄 알았으나 의외로 시간이 많이 걸리지는 않는다.

 

정답 코드

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

using namespace std;

int n, sx, sy;

int dx[] = {-1, 0, 0, 1};
int dy[] = {0, -1, 1, 0};

struct Pos {
	int x, y, dist, body, eat;
};

int bfs(Pos start, vector<vector<int>>& lst) {
    int total_time = 0;

    while (true) {
        vector<vector<int>> dist(n, vector<int>(n, -1));
        queue<Pos> q;
        q.push(start);
        dist[start.x][start.y] = 0;

        vector<Pos> fishes;
        int min_dist = -1;

        while (!q.empty()) {
            Pos now = q.front();
            q.pop();
            int x = now.x, y = now.y, d = now.dist;

            for (int i = 0; i < 4; ++i) {
                int nx = x + dx[i], ny = y + dy[i];
                if (nx >= 0 && nx < n && ny >= 0 && ny < n && dist[nx][ny] == -1 && lst[nx][ny] <= now.body) {
                    dist[nx][ny] = d + 1;
                    q.push({ nx, ny, d + 1, now.body, now.eat });

                    if (lst[nx][ny] > 0 && lst[nx][ny] < now.body) {
                        if (min_dist == -1 || d + 1 < min_dist) {
                            min_dist = d + 1;
                            fishes.clear();
                            fishes.push_back({ nx, ny, d + 1, now.body, now.eat });
                        }
                        else if (d + 1 == min_dist) {
                            fishes.push_back({ nx, ny, d + 1, now.body, now.eat });
                        }
                    }
                }
            }
        }

        if (fishes.empty()) {
            return total_time;
        }

        sort(fishes.begin(), fishes.end(), [](const Pos& a, const Pos& b) {
            if (a.x != b.x) return a.x < b.x;
            return a.y < b.y;
            });

        Pos chosen_fish = fishes[0];
        total_time += chosen_fish.dist;
        start = { chosen_fish.x, chosen_fish.y, 0, chosen_fish.body, chosen_fish.eat + 1 };

        if (start.eat == start.body) {
            start.body++;
            start.eat = 0;
        }

        lst[chosen_fish.x][chosen_fish.y] = 0;
    }
}

int main() {
	cin >> n;
	vector<vector<int>> lst(n, vector<int>(n));
	Pos pos;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> lst[i][j];
			if (lst[i][j] == 9) {
				pos = { i, j, 0, 2, 0 };
				lst[i][j] = 0;
			}
		}
	}
	cout << bfs(pos, lst);
}