백준 16236번 아기상어 (BFS)

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

16236번: 아기 상어

 

맵 형태로 상어가 가까운 거리의 물고기를 먹어야하므로 BFS를 통해 구현하는 것이 적합해보인다.

 

그럼 BFS를 통해 가장 가까운 거리의 물고기를 탐색하면서 해당 물고기를 먹고, 상어의 위치를 계속 업데이트 해주는 방식으로 구현해보자.

같은 거리의 물고기가 여러 마리일 경우 위쪽 물고기, 행도 같을 경우 왼쪽 물고기를 먹어야한다고 명시되어 있으므로, 여러 마리인 경우에는 행 값이 작은 물고기 다음으로 열 값이 작은 물고기를 먹으면 된다.

본인은 vector의 sort를 이용하여 오름차순으로 정렬한 뒤, 0인 인덱스 값을 넣었다. (소스코드 참조, vector v변수)

 

중요한 부분은 맵의 현재 값에서 다음 값으로 탐색할 때, 예외처리가 많이 들어간다.

같은 거리의 물고기가 있는 경우를 체크하기 위해 flag 변수를 이용하였으며, flag에 거리를 입력하고 다음 물고기가 flag 값을 넘어서지 않는 경우에만 v vector에 추가하였다.

 

마지막으로 상어 위치를 업데이트 할 때, eat 변수를 이용하여 상어 크기만큼 물고기를 먹었다면 상어 크기를 업데이트 해주고 eat 변수를 0으로 초기화한다.

 

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

using namespace std;

int n;
int map[20][20];
int visited[20][20];

int dx[4] = { 1,-1,0,0 };
int dy[4] = { 0,0,1,-1 };

queue<pair<int, int>> q;

int shark_size = 2;
int shark_x, shark_y;
int eat;
int ans;


bool bfs() {
	memset(visited, 0, sizeof(visited));
	visited[shark_x][shark_y] = 1;
	int flag = 0;
	vector<pair<int, int>> v;

	while (!q.empty()) {
		int cx = q.front().first;
		int cy = q.front().second;
		q.pop();

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

			if (nx < 0 || ny < 0 || nx >= n || ny >= n) continue;

			if (visited[nx][ny] == 0 && map[nx][ny] <= shark_size) {
				if (flag == 0) {
					q.push(make_pair(nx, ny));
					visited[nx][ny] = visited[cx][cy] + 1;
				}
				if (map[nx][ny] != 0 && map[nx][ny] < shark_size) {
					if (flag == 0) {
						v.push_back(make_pair(nx, ny));
						visited[nx][ny] = visited[cx][cy] + 1;
						flag = visited[nx][ny];
					}
					else {
						if (flag > visited[cx][cy]) {
							v.push_back(make_pair(nx, ny));
							visited[nx][ny] = visited[cx][cy] + 1;
							flag = visited[nx][ny];
						}
					}
				}
			}
		}
	}

	if (flag != 0 ) {
		sort(v.begin(), v.end());
		shark_x = v[0].first; shark_y = v[0].second;
		ans += visited[shark_x][shark_y]-1;
		eat++;

		if (shark_size == eat) {
			shark_size++;
			eat = 0;	
		}
		return true;
	}
	else {
		return false;
	}
}

int main(void) {
	cin >> n;

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> map[i][j];

			if (map[i][j] == 9) {
				q.push(make_pair(i, j));
				map[i][j] = 0;
				shark_x = i, shark_y = j;
				visited[i][j] = 1;
			}
		}
	}

	while (true) {
		if (bfs() == false) {
			break;
		}
		
		q.push(make_pair(shark_x, shark_y));
		map[shark_x][shark_y] = 0;
	}

	cout << ans << '\n';

	return 0;
}