[백준 16236번 C/C++] 아기 상어

 

[백준 16236번 C/C++] 아기 상어 

 

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

---

 

 

해결전략

 

너비우선탐색 BFS

 

 

아기 상어가 물고기를 먹은 시점에 BFS를 다시 돌려야 한다.

---

 

 

처음 시도한 코드

 

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int dirY[4] = { -1, 0, 1, 0 };
int dirX[4] = { 0, -1, 0, 1 };

int n;
vector<vector<int>> v;
int answer;
bool success = false;

struct Info{
	int y, x, feed, sharkSize;
};

void BFS(int startY, int startX, int feed, int size, int time)
{
	int timeSpent = 0;

	queue<Info> Q;
	Q.push({ startY, startX, feed, size });
	vector<vector<int>> duration(n, vector<int>(n, -1));
	vector<vector<bool>> visited(n, vector<bool>(n, false));
	duration[startY][startX] = 0;
	visited[startY][startX] = true;

	while (!Q.empty())
	{
		int y = Q.front().y;
		int x = Q.front().x;
		int feed = Q.front().feed;
		int sharkSize = Q.front().sharkSize;
		Q.pop();

		for (int i = 0; i < 4; i++) {
			int ny = y + dirY[i];
			int nx = x + dirX[i];

			if (ny < 0 || n <= ny || nx < 0 || n <= nx) continue;
			if (visited[ny][nx] == true) continue;
			if (sharkSize < v[ny][nx]) continue;

			if (sharkSize == v[ny][nx] || v[ny][nx] == 0) {
				Q.push({ ny, nx, feed, sharkSize }); // 이동만 함.
				duration[ny][nx] = duration[y][x] + 1;
				visited[ny][nx] = true;
				continue;
			}

			//cout << ny << ", " << nx << "\n";

			// 물고기를 잡아먹는 경우
			feed++;
			v[ny][nx] = 0; // 먹은 물고기 표시
			duration[ny][nx] = duration[y][x] + 1;
			visited[ny][nx] = true;

			timeSpent = max(timeSpent, duration[ny][nx]);
			answer = max(answer, time + timeSpent);
			success = true;

			if (feed == sharkSize) {
				BFS(ny, nx, 0, sharkSize + 1, time + timeSpent);
			}
			else {
				BFS(ny, nx, feed, sharkSize, time + timeSpent);
			}
		}
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	cin >> n;
	v.resize(n, vector<int>(n));

	int startY, startX;
	for (int y = 0; y < n; y++){
		for (int x = 0; x < n; x++) {
			cin >> v[y][x];
			if (v[y][x] == 9){
				startY = y;
				startX = x;
				v[y][x] = 0; // 상어가 처음 위치한 칸을 빈칸으로 설정
			}
		}
	}

	BFS(startY, startX, 0, 2, 0);

	if (false == success){
		cout << "0";
	}
	else{
		cout << answer << "\n";
	}

	return 0;
}

 

---

 

 

정답코드

 

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

struct Info { // 상어의 위치, 먹은 물고기 수, 상어의 크기, 경과 시간
    int y, x, feed, sharkSize, time;
};

int dirY[4] = { -1, 0, 1, 0 };
int dirX[4] = { 0, -1, 0, 1 };

int n;
vector<vector<int>> v; 		  // 공간의 상태를 나타내는 2차원 벡터
vector<vector<bool>> visited; // 방문 여부를 저장하는 2차원 벡터
int answer = 0; 			  // 최종 결과(경과 시간)를 저장할 변수

void BFS(int startY, int startX)
{
    queue<Info> Q;
    Q.push({ startY, startX, 0, 2, 0 }); // 초기 상어의 위치, 먹은 물고기 수, 크기, 시간을 큐에 삽입
    visited[startY][startX] = true; // 시작 위치를 방문 처리

    while (!Q.empty()) {
        int size = Q.size();
        vector<Info> fish; // 먹을 수 있는 물고기를 저장할 벡터

        for (int i = 0; i < size; ++i) 
        {
            int y = Q.front().y;
            int x = Q.front().x;
            int feed = Q.front().feed;
            int sharkSize = Q.front().sharkSize;
            int time = Q.front().time;
            Q.pop();

            // 먹을 수 있는 물고기를 발견한 경우
            if (v[y][x] != 0 && v[y][x] < sharkSize) {
                fish.push_back({ y, x, feed, sharkSize, time });
                continue;
            }

            for (int j = 0; j < 4; ++j) { // 상하좌우로 이동
                int ny = y + dirY[j];
                int nx = x + dirX[j];
			
            	if (ny < 0 || n <= ny || nx < 0 || n <= nx) continue;
                if (visited[ny][nx] || v[ny][nx] > sharkSize) continue; // 이동 불가능한 경우

                visited[ny][nx] = true; // 방문 처리
                Q.push({ ny, nx, feed, sharkSize, time + 1 }); // 큐에 삽입
            }
        }

        // 먹을 수 있는 물고기가 있는 경우
        if (!fish.empty()) {
            // 물고기를 시간, 행, 열 순으로 정렬
            sort(fish.begin(), fish.end(), [](const Info& a, const Info& b) {
                if (a.time == b.time) {
                    if (a.y == b.y) return a.x < b.x;
                    return a.y < b.y;
                }
                return a.time < b.time;
            });

            // 가장 우선순위가 높은 물고기를 먹음
            int newY = fish[0].y;
            int newX = fish[0].x
			int newFeed = fish[0].feed + 1;
            int newSize = fish[0].sharkSize;
            int newTime = fish[0].time;

            if (newFeed == newSize) {
                newFeed = 0;
                newSize++;
            }

            v[newY][newX] = 0; // 먹은 물고기 제거
            answer = newTime; // 시간 업데이트
            visited.assign(n, vector<bool>(n, false)); // 방문 배열 초기화
            Q = queue<Info>(); // 큐 초기화
            Q.push({ newY, newX, newFeed, newSize, newTime });
            visited[newY][newX] = true;
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n;
    v.resize(n, vector<int>(n));
    visited.assign(n, vector<bool>(n, false));

    int startY, startX;
    for (int y = 0; y < n; y++) {
        for (int x = 0; x < n; x++) {
            cin >> v[y][x];
            if (v[y][x] == 9) {
                startY = y;
                startX = x;
                v[y][x] = 0; // 상어가 처음 위치한 칸을 빈칸으로 설정
            }
        }
    }

    BFS(startY, startX);

    cout << answer << "\n";

    return 0;
}

 

 

 

 

---