[BOJ]16236번 아기 상어

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

16236번: 아기 상어

 

아이디어

1, bfs방식으로 아기 상어의 위치를 시작으로 지도를 순회한다.

 

2, 한 번씩 움직일 때마다 아기 상어가 물고기를 먹었는지 판별

- 2개의 큐로 관리

- 큐 하나는 움직이기 전 상태, 다른 하나는 움직인 후의 상태를 저장하여 물고기를 먹었는지 판별

- 움직인 후의 큐에 대하여 먹을 수 있는 물고기의 위치에 도달하였을 시 벡터에 저장을 하고 문제 조건에 따라 맨 위 오른쪽인 위치부터 정렬하여 먹은 물고기 위치를 갱신, 그 후 큐에는 현재 위치만 저장을 하고 다시 새롭게 bfs탐색을 시작

- 움직인 후의 큐에 대하여 먹을 수 있는 물고기의 위치에 도달을 못하였을 시 다시 원래 큐에 저장을 하고 계속적으로 bfs탐색

 

#include <cstdio>
#include <queue>
#include <cstring>
#include <algorithm>
using namespace std;

int map[21][21];
int visited[21][21];

int N;
int dr[4] = { 1,0,-1,-0 };
int dc[4] = { 0,1,0,-1 };

typedef struct location{
	int r;
	int c;
	int size;
	int depth;
	int eat_check;
}location;

queue<location> q;
queue<location> temp_q;

bool sort_location(location a, location b) {

	if (a.r < b.r) {
		return true;
	}
	else if (a.r == b.r) {
		if (a.c < b.c) return true;
		else return false;
	}

	return false;
}

int main() {
	int res = 0;
	int nr, nc;
	int check = 0;
	scanf("%d", &N);

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			scanf("%d", &map[i][j]);

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

	
	while (!q.empty()) {
		check = 0;
		while (!temp_q.empty()) temp_q.pop();

		while (!q.empty()) {
			location search = q.front();
			q.pop();

			for (int i = 0; i < 4; i++) {
				nr = search.r + dr[i];
				nc = search.c + dc[i];

				if (nr < 0 || nr >= N || nc < 0 || nc >= N) {
					continue;
				}

				if (visited[nr][nc] == 1) continue;

				if (map[nr][nc] == 0 && visited[nr][nc] == 0) {
					temp_q.push({ nr,nc,search.size,search.depth + 1,search.eat_check });
					visited[nr][nc] = 1;
				}
				else if (map[nr][nc] == search.size && visited[nr][nc] == 0) {
					temp_q.push({ nr,nc,search.size,search.depth + 1,search.eat_check });
					visited[nr][nc] = 1;
				}
				else if (map[nr][nc] < search.size && visited[nr][nc] == 0) {
					check = 1;
					temp_q.push({ nr,nc,search.size,search.depth + 1,search.eat_check });
					visited[nr][nc] = 1;
				}
				
			}

		}

		if (check == 0) {
			q = temp_q;
		}
		else {

			vector<location> temp;

			//새로운 위치 출발점을 갱신
			while (!temp_q.empty()) {
				location search = temp_q.front();
				temp_q.pop();

				if (map[search.r][search.c] < search.size && map[search.r][search.c] != 0) {
					temp.push_back(search);
				}
			}

			sort(temp.begin(), temp.end(), sort_location);

			location detect = temp[0];
			map[detect.r][detect.c] = 0;
			memset(visited, 0, sizeof(visited));
			res = detect.depth;

			if (detect.eat_check + 1 == detect.size) {
				q.push({ detect.r,detect.c,detect.size + 1,detect.depth,0 });
				visited[detect.r][detect.c] = 1;
			}
			else {
				q.push({ detect.r,detect.c,detect.size,detect.depth,detect.eat_check+1});
				visited[detect.r][detect.c] = 1;
			}
		}
	}

	printf("%d\n", res);

	return 0;
}