백준 16236_아기 상어(C++)

 

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

16236번: 아기 상어

[문제 풀이]

시뮬레이션을 이용하여 문제를 풀었습니다.

이 문제는

• 더 이상 먹을 수 있는 물고기가 공간에 없다면 아기 상어는 엄마 상어에게 도움을 요청한다.
• 먹을 수 있는 물고기가 1마리라면, 그 물고기를 먹으러 간다.
• 먹을 수 있는 물고기가 1마리보다 많다면, 거리가 가장 가까운 물고기를 먹으러 간다.
  • 거리는 아기 상어가 있는 칸에서 물고기가 있는 칸으로 이동할 때, 지나야하는 칸의 개수의 최솟값이다.
  • 거리가 가까운 물고기가 많다면, 가장 위에 있는 물고기, 그러한 물고기가 여러마리라면, 가장 왼쪽에 있는 물고기를 먹는다.

이 과정을 순차적으로 구현해주는 것이 핵심입니다. 이 과정을 구현하기 위해 BFS를 이용하여 상어가 갈 수 있는 다음 위치를 큐에 넣어 주었고 다음 물고기의 위치가 정해지면 큐에 있는 값들을 빼기 전에 같은 거리에 있지만 가장 위에 있는 물고기 혹은 위에 있는 물고기 중에 왼쪽에 있는 물고기가 있는지 확인해 주었습니다.

[코드]

#include<iostream>
#include<queue>
#include<tuple>

using namespace std;

int N, result = 0;
int shark = 2, eat = 0; 
int map[21][21];
bool visit[21][21] = { false, };
queue<tuple<int, int, int>> que;

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

void bfs();

int main() {

	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){
				que.push(make_tuple(i, j, 0));
				map[i][j] = 0;
				visit[i][j] = 1;
				
			}
		}
	}

	while (!que.empty()) {

		int x = get<0>(que.front());
		int y = get<1>(que.front());
		int cnt = get<2>(que.front());
		que.pop();

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

			if (nx < 0 || ny < 0 || nx >= N || ny >= N || map[nx][ny] > shark)
				continue;

			if (map[nx][ny] < shark && map[nx][ny] != 0 && !visit[nx][ny]) {

				while (!que.empty()) {
					for (int temp = 0; temp < 4; temp++) {
						int temp_x = get<0>(que.front()) + dx[temp];
						int temp_y = get<1>(que.front()) + dy[temp];

						if (map[temp_x][temp_y] < shark && map[temp_x][temp_y] != 0 && !visit[temp_x][temp_y]) {

							int count = get<2>(que.front());

							if (count == cnt) {
								if (temp_x < nx) {
									nx = temp_x;
									ny = temp_y;
								}
								else if (temp_x == nx) {
									if (temp_y < ny) {
										nx = temp_x;
										ny = temp_y;
									}
								}

							}
						}
					}

					que.pop();
				}

				result += cnt + 1;
				eat++;

				if (eat == shark) {
					eat = 0;
					shark++;
				}

				for (int j = 0; j < N; j++) {
					for (int k = 0; k < N; k++) {
						visit[j][k] = false;
					}
				}

				map[nx][ny] = 0;
				visit[nx][ny] = true;
				que.push(make_tuple(nx, ny, 0));
				break;

			}
			else if (map[nx][ny] <= shark && !visit[nx][ny]) {

				visit[nx][ny] = true;
				que.push(make_tuple(nx, ny, cnt + 1));
			}

		}


	}

	printf("%d\n", result);
	return 0;

}