https://www.acmicpc.net/problem/16236
이 문제는 솔직히 설명이 겁나 불친절하다
정확히 이문제는 핵심이 나를 기준으로 나보다 크기가 작고 같은 거리에 있는 물고기 들은 위에에서 왼쪽부터 오른쪽 까지 검사하고 내려와서 왼쪽부터 오른쪽 까지 검사하면서 이 순으로 탐색을 하는 거였다.
단 위에를 듣고 BFS 이동방향을 1,0 ->0,-1 ->0,1 ->-1,0 이렇게 만 하면 안풀린다
while (!bfsQ.empty()) {
otherX = bfsQ.front().second.first;
otherY = bfsQ.front().second.second;
otherCost = bfsQ.front().first;
if (CanEat(otherX, otherY) && otherCost<=cost) {
if (otherX < startX) {
startX = otherX;
startY = otherY;
otherCost = cost;
}
else if (otherX == startX && startY>otherY ) {
startX = otherX;
startY = otherY;
otherCost = cost;
}
}
핵심은 이부분이다 내가 물고기를 먹을 수있는 지역으로 갔을 때 현재 큐에 들어와 있는 것중 나보다 거리가 작거나 같고 행의 값이 위에 있거나 혹은 행이 같다면 열값이 더 먼저인 애를 찾아서 거기를 가야한다 이에 의해 필자는 행을 검사에서 위에있으면 해당 행으로 탐색지점을 바꿔줬고 같다면 열값이 더 작은 쪽으로 옮겨줬다
#include <iostream>
#include <queue>
using namespace std;
int n;
int arr[20][20] = { 0, };
bool isVisited[20][20];
int fishSize = 2;
int eatFish = 0;
int cnt = 0;
queue<pair<int,pair<int, int>>> bfsQ;
bool CanEat(int x, int y) {
if (arr[x][y]>0&&arr[x][y] < fishSize) {
return true;
}
return false;
}
bool canGo(int x, int y) {
if (x >= 0 && x < n && y >= 0 && y < n && !isVisited[x][y] && (CanEat(x, y) || arr[x][y] == 0 || arr[x][y]==fishSize))
return true;
else
return false;
}
void Bfs(int x, int y) {
bfsQ.push({ cnt,{x,y} });
arr[x][y] = 0;
int startX, startY, cost;
int otherX, otherY, otherCost;
while (!bfsQ.empty()) {
startX = bfsQ.front().second.first;
startY = bfsQ.front().second.second;
cost = bfsQ.front().first;
bfsQ.pop();
if (CanEat(startX, startY)) {
cnt += cost;
while (!bfsQ.empty()) {
otherX = bfsQ.front().second.first;
otherY = bfsQ.front().second.second;
otherCost = bfsQ.front().first;
if (CanEat(otherX, otherY) && otherCost<=cost) {
if (otherX < startX) {
startX = otherX;
startY = otherY;
otherCost = cost;
}
else if (otherX == startX && startY>otherY ) {
startX = otherX;
startY = otherY;
otherCost = cost;
}
}
bfsQ.pop();
}
bfsQ.push({ 0, {startX, startY}});
eatFish += 1;
if (eatFish == fishSize) {
fishSize += 1;
eatFish = 0;
}
arr[startX][startY] = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
isVisited[i][j] = false;
}
}
isVisited[startX][startY] = true;
cost = 0;
}
if (canGo(startX-1,startY)) {
bfsQ.push({ cost + 1,{startX -1,startY}});
isVisited[startX - 1][startY] = 1;
}
if (canGo(startX, startY-1)) {
bfsQ.push({ cost + 1,{startX ,startY - 1} });
isVisited[startX][startY-1] = 1;
}
if (canGo(startX , startY+1)) {
bfsQ.push({ cost + 1,{startX ,startY + 1} });
isVisited[startX][startY + 1] = 1;
}
if (canGo(startX+1 , startY)) {
bfsQ.push({ cost + 1,{startX + 1,startY} });
isVisited[startX + 1][startY] = 1;
}
}
}
int main() {
cin >> n;
int startIdxCol, startIdxRow;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cin >> arr[i][j];
if (arr[i][j] == 9) {
startIdxCol = i;
startIdxRow = j;
}
}
}
Bfs(startIdxCol, startIdxRow);
cout << cnt;
}
