득이공간
[백준 C++] 16236 아기 상어 - 너비우선탐색 본문
#include <iostream>
#include <queue>
#include <cstring>
using namespace std;
typedef pair<int, int> p;
typedef pair<pair<int, int>, int> pp;
const int DX[4] = { -1, 0, 1, 0 };
const int DY[4] = { 0, -1, 0, 1 };
int N;
int Bowl[20][20];
bool Visited[20][20];
int Time, Ate;
int Size = 2;
int Row, Col;
bool Target(int R, int C, int D, int FR, int FC, int FD)
{
if (Bowl[R][C] < Size
&& Bowl[R][C] != 0
&& D <= FD
&& ((R < FR) || (R == FR && C < FC)))
{
return true;
}
return false;
}
pp BFS()
{
memset(Visited, false, sizeof(Visited));
int FR = N;
int FC = N;
int FD = 1000;
queue<pp> SQ;
Visited[Row][Col] = true;
SQ.emplace(p(Row, Col), 0);
while (!SQ.empty())
{
int R = SQ.front().first.first;
int C = SQ.front().first.second;
int D = SQ.front().second;
SQ.pop();
for (int i = 0; i < 4; ++i)
{
int NR = R + DY[i];
int NC = C + DX[i];
if (NR < 0 || NR > N - 1 || NC < 0 || NC > N - 1
|| Visited[NR][NC] || Bowl[NR][NC] > Size)
{
continue;
}
Visited[NR][NC] = true;
if (Target(NR, NC, D + 1, FR, FC, FD))
{
FR = NR;
FC = NC;
FD = D + 1;
}
else
{
SQ.emplace(p(NR, NC), D + 1);
}
}
}
return pp(p(FR, FC), FD);
}
bool EatFish()
{
pp Min = BFS();
if (Min.second == 1000)
{
return false;
}
Bowl[Row][Col] = 0;
Row = Min.first.first;
Col = Min.first.second;
Bowl[Row][Col] = 9;
Time += Min.second;
++Ate;
if (Ate == Size)
{
Ate = 0;
++Size;
}
return true;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr); cout.tie(nullptr);
cin >> N;
for (int i = 0; i < N; ++i)
{
for (int j = 0; j < N; ++j)
{
cin >> Bowl[i][j];
if (Bowl[i][j] == 9)
{
Row = i;
Col = j;
}
}
}
while (EatFish()) {}
cout << Time;
}
시뮬레이션 & BFS 문제입니다.
아기 상어가 먹이를 더이상 먹을 수 없을 때까지 먹이를 찾고 먹는 행동을 반복하도록 해야 합니다.
풀이 과정은 다음과 같습니다.
1. 너비 우선 탐색을 이용해 가장 가까운 먹이 탐색 및 선택
1-a. 먹이는 상어보다 크기가 작아야 함
1-b. 거리가 같은 먹이가 여러개면 위쪽, 왼쪽 위치 순으로 우선 선택
2. 목표로 지정한 먹이의 위치로 상어 이동
3. 시간 증가 및 누적 먹이량에 따른 상어 크기 조정
'PS > 알고리즘 문제풀이' 카테고리의 다른 글
[백준 C++] 1918 후위 표기식 - 스택 (0) | 2024.03.18 |
---|---|
[백준 C++] 1167 트리의 지름 - 트리 (0) | 2024.03.18 |
[백준 C++] 11779 최소비용 구하기 2 - 다익스트라 (2) | 2024.03.17 |
[백준 C++] 2638 치즈 - 너비우선탐색 (1) | 2024.03.17 |
[백준 C++] 17144 미세먼지 안녕! - 구현 (0) | 2024.03.14 |