[BAE/<JOON> 문제풀이] 16236. 아기상어

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

16236번: 아기 상어

오랜만에 백준문제를 풀어봤다.

 

간단한 BFS문제여서 금방 풀 줄 알았는데 한가지 코너 케이스가 있어서 그거 찾고 수정하느라 좀 오래걸렸다.

 

보통 BFS에서 탐색 방향을 지정할 때 배열에 {1, 0, -1, 0} {0, 1, 0, -1} 이런식으로 다음 큐에 삽입할 때 현재 노드에 추가할 정보를 써놓은 후,

 

저 배열의 순서를 바꿔서 우선적으로 나아갈 방향을 정한다.

 

하지만 이 문제에선 가장 가까운 물고기 중에서 가장 높거나 낮은 물고기를 골라야하기 때문에 몇몇 테스트 케이스에서 

 

오답이 발생한다. 

 

예를 들자면

 

a * b 1

2 0 0 0

0 0 3 0

0 4 0 0

 

위와 같이 *가 상어의 현재 위치이고 숫자가 먹으려는 물고기들이라고 가정해보자.

 

가장 가까이 있는 물고기를 먹어야 하므로 1, 2번 물고기가 대상이 될 것이다. 

 

또한 탐색 우선 순위는 위 -> 왼쪽 -> 나머지로 문제에서 정해져있기 때문에 먹어야하는 물고기는 1번이다. 

 

여기서 애매한 문제가 발생하게된다. 

 

노드를 위 -> 왼쪽 으로 탐색하기 때문에 a노드가 b노드보다 먼저 큐에 들어갈 것이다. 

 

즉, 단순히 탐색 방향을 지정하고 가장 빨리 발견되는 먹이를 먹게 된다면 a가 먼저 큐에서 나와 상어는 2번 먹이를 먹게되고 만다. 

 

굉장히 단순하고 찾기만 한다면 금방 고칠 수 있는 문제이지만

 

난 평소에 넓이 우선 탐색 문제를 풀면서 탐색방향은 단순하게 추가 노드 생성시 사용되는 배열로 정한다고만 생각해서 

 

이러한 오류가 발생했다. 

 

코드::

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

using namespace std;

int mvx[5] = { 0, -1, 0, 0, 1 };
int mvy[5] = { 0, 0, -1, 1, 0 };

int bsize = 2;
int pcount = 0;
int N;
int bst = 0;

int ccc = 1;

vector<vector<int > > arr;
vector<vector<int > > ch;

struct baby {
	int x, y, mvc;
};

baby find_next_pray(baby now) {
	queue<baby> q;
	q.push(now);
	vector<baby> clist;
	int cleng = 999;
	bool cch = false;
	while (!q.empty()) {
		int nx = q.front().x;
		int ny = q.front().y;
		int mc = q.front().mvc;
		q.pop();
		if (cch && mc >= cleng) continue; // 현재 발견된 거리보다 멀면 무시		
		for (int i = 1; i <= 4; i++) {
			int mx = nx + mvx[i];
			int my = ny + mvy[i];
			if (mx < 1 || my < 1 || mx > N || my > N || ch[mx][my] == 1 || arr[mx][my] > bsize) continue;
			q.push(baby{ mx, my, mc + 1 });
			ch[mx][my] = 1;
			if (arr[mx][my] < bsize && arr[mx][my] > 0) {
				//cout << cc++ << ". " << mx << " " << my << "::" << mc + 1 << endl;																
				cch = true;
				cleng = mc + 1;
				clist.push_back(baby{ mx, my, mc + 1 });
				//return { baby {mx, my}, mc + 1 };
			}
		}
	}

	if (cch) {
		for (int i = 1; i <= N; i++) {
			for (int j = 1; j <= N; j++) {
				for (auto cc : clist) {
					if (cc.x == i && cc.y == j) {
						if (++bst == bsize) {
							bsize++;
							bst = 0;
							//cout << "shark size::" << bsize << endl;
						}
						
						arr[i][j] = 0;
						/*cout << endl;
						cout << "no. " << ccc++ << endl;
						cout << "size:" << bsize << endl;
						for (int k = 1; k <= N; k++) {
							for (int l = 1; l <= N; l++) {
								if (k == i && l == j) {
									cout << "* ";
									continue;
								}
								cout << arr[k][l] << " ";
							}
							cout << endl;
						}*/
						return cc;
					}
				}
			}
		}
	}

	return { -1, -1, -1 };
}


int main()
{
	cin >> N;

	baby now = { 0, 0, 0 };

	arr.resize(N + 1);
	ch.resize(N + 1);
	for (int i = 1; i <= N; i++) {
		arr[i].resize(N + 1);
		ch[i].resize(N + 1);
		for (int j = 1; j <= N; j++) {
			cin >> arr[i][j];
			if (arr[i][j] == 9) {
				now = { i, j, 0 };
				arr[i][j] = 0;				
			}			
			if (arr[i][j] <= 6 && arr[i][j] >= 1) pcount++;
		}
	}

	baby np;
	int dp = 0;
	while ((np = find_next_pray(now)).mvc != -1) {
		for (int i = 1; i <= N; i++) {
			for (int j = 1; j <= N; j++) {
				ch[i][j] = 0;
			}
		}
		dp += np.mvc;	
		now = { np.x, np.y, 0 };
	}	

	cout << dp;

	return 0;
}