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

코드1

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

using namespace std;

// 아기 상어의 크기는 2
// 0은 빈칸, 1,2,3,4,5,6은 물고기의 크기 9는 상어
// 먹을 수 있는 물고기가 1마리라면 그 물고기를 먹음
// 먹을 수 있는 물고기가 여러 마리라면 가장 가까이에 있는 물고기 먹음
// 거리가 가까운 물고기가 많다면 가장 위에 있는 물고기, 그런 게 많다면 가장 왼쪽에 있는 물고기를 먹음 (> 사용)
// 이동 시 1초, 물고기를 먹으면 빈 칸
// 아기상어는 자신의 크기와 같은 수의 물고기를 먹으면 크기 1 증가
// 자신의 크기보다 큰 물고기 칸 통행 X, 나머지칸 지나감
// 먹는 것은 자기보다 작은 물고기만
// 거리는 bfs로 찾자
const int dx[] = { 1,-1,0,0 };
const int dy[] = { 0,0,-1,1 };
int n, a[23][23], babyshark = 2, eat, res, dist, visited[23][23];
pair<int, int> sharkpos;

void bfs(int x, int y) {
	memset(visited, 0, sizeof(visited));
	queue<pair<int, int>> q;
	q.push(make_pair(x, y));
	visited[x][y] = 1;
	while (!q.empty()) {
		int px = q.front().first;
		int py = q.front().second;
		q.pop();
		for (int i = 0; i < 4; i++) {
			int nx = px + dx[i];
			int ny = py + dy[i];
			if (nx >= n || ny >= n || nx < 0 || ny < 0 || visited[nx][ny] || a[nx][ny] > babyshark) continue;
			visited[nx][ny] = visited[px][py] + 1;
			q.push(make_pair(nx, ny));
		}
	}
}

// 거리 구하고, 순회 돌리면서 거리 가깝고 덩치 작은 물고기 먹기

void go() {
	int tmp = 987654321;
	pair<int, int> pr;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (tmp > visited[i][j] && visited[i][j] > 0 && a[i][j] < babyshark && a[i][j] != 0) {
				tmp = visited[i][j];
				pr.first = i;
				pr.second = j;
			}
		}
	}
	if (tmp == 987654321) {
		dist = 987654321;
		return;
	}
	dist = visited[pr.first][pr.second] - 1;
	a[pr.first][pr.second] = 0;
	sharkpos.first = pr.first;
	sharkpos.second = pr.second;
}

// check함수는 덩치가 다 크면 break
// 또는 물고기가 아무것도 안남았다면 break

bool checkcnt() {
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if ((a[i][j] >= 1 && a[i][j] <= 6)) return false;
		}
	}
	return true;
}

bool checksize() {
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (a[i][j] < babyshark) return false;
		}
	}
	return true;
}

int main() {
	cin >> n;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> a[i][j];
			if (a[i][j] == 9) {
				sharkpos.first = i;
				sharkpos.second = j;
				a[i][j] = 0;
			}
		}
	}

	while (1) {
		if (checkcnt() || checksize()) break;
		bfs(sharkpos.first, sharkpos.second);
		go();
		if (dist == 987654321) break;
		eat++;
		res += dist;
		if (eat == babyshark) {
			babyshark++;
			eat = 0;
		}
	}

	cout << res << '\n';
	return 0;
}

코드 2

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

using namespace std;

const int dx[] = {1, -1, 0, 0};
const int dy[] = {0, 0, -1, 1};
int n, a[23][23], babySharkSize = 2, eatCount = 0, totalTime = 0;
pair<int, int> sharkPos;

struct Fish {
    int x, y, dist;
    bool operator<(const Fish& other) const {
        if (dist == other.dist) {
            if (x == other.x) return y < other.y; // 가장 왼쪽 우선
            return x < other.x; // 가장 위쪽 우선
        }
        return dist < other.dist; // 거리가 가장 가까운 것 우선
    }
};

int bfs() {
    queue<pair<int, int>> q;
    vector<vector<int>> visited(n, vector<int>(n, 0));
    vector<Fish> fishes;

    q.push(sharkPos);
    visited[sharkPos.first][sharkPos.second] = 1;

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

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

            if (nx >= 0 && ny >= 0 && nx < n && ny < n && !visited[nx][ny] && a[nx][ny] <= babySharkSize) {
                visited[nx][ny] = visited[x][y] + 1;
                q.push({nx, ny});

                if (a[nx][ny] > 0 && a[nx][ny] < babySharkSize) {
                    fishes.push_back({nx, ny, visited[nx][ny] - 1});
                }
            }
        }
    }

    if (fishes.empty()) return 0; // 더 이상 먹을 물고기가 없음

    sort(fishes.begin(), fishes.end()); // 조건에 맞는 물고기 정렬
    Fish target = fishes[0];

    // 상어 위치 및 상태 업데이트
    totalTime += target.dist;
    sharkPos = {target.x, target.y};
    a[target.x][target.y] = 0; // 물고기를 먹은 위치는 빈칸으로

    eatCount++;
    if (eatCount == babySharkSize) { // 아기 상어의 크기 증가 조건
        babySharkSize++;
        eatCount = 0;
    }

    return target.dist;
}

int main() {
    cin >> n;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> a[i][j];
            if (a[i][j] == 9) {
                sharkPos = {i, j};
                a[i][j] = 0; // 상어 초기 위치를 빈칸으로 설정
            }
        }
    }

    while (true) {
        int dist = bfs();
        if (dist == 0) break; // 먹을 수 있는 물고기가 없을 때 종료
    }

    cout << totalTime << '\n';
    return 0;
}

풀이