백준 16236번 아기상어

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

16236번: 아기 상어

 

 

 

 

 

<접근방법>

bfs 탐색으로 시뮬레이션하는 문제입니다.

처음에 큐에 넣는 순서를 조건대로 해준 다음에 먹이를 만나면 바로 먹는 것으로 처리를 하였습니다.

구현이 짧아진다는 것에 흥분하여 생각이 짧아진 거 같습니다.

새로운 발견에는 흥분이 아니라 의심을 해야겠습니다.

 

결국 먹이 먹는 순서 조건을 어떻게 구현할지가 관건이었던 것 같습니다.

sort기준을 조건대로 구현한 우선순위 큐에 넣어서 해결을 하거나

거리가 같은 먹이들을 따로 저장한 다음, 오름차순 정렬을 수행한 후 첫 번째 먹이를 먹는 식으로

구현을 하면 되겠습니다.

저는 문제를 풀 때, 시간이 촉박하여 투박하게 구현하였습니다.

 

 

 

---

 

 

 

<코드>

#include <iostream>
#include <algorithm>
#include <queue>
#include <memory.h>
using namespace std;

struct point {
	int y, x;
};

struct info {
	int y, x, sz, exp;
};

int n, map[20][20];
int time;
int dy[4] = { -1, 0, 0, 1 };
int dx[4] = { 0, -1, 1, 0 };
int debug[20][20];
int d = 1;

info s;

void eat(queue<point> die) {
	int y = die.front().y;
	int x = die.front().x;

	while (!die.empty()) {
		point t = die.front();
		die.pop();

		if (t.y < y) {
			y = t.y;
			x = t.x;
		}
		else if (t.y == y) {
			if (t.x < x) {
				y = t.y;
				x = t.x;
			}
		}
	}
	map[y][x] = 0;
	s.y = y; s.x = x; s.exp++;
}

int bfs() {
	queue<point> q;
	queue<point> die;
	int tres = 0;
	int visit[20][20] = {0, };
	memset(visit, 0, sizeof(visit));

	q.push({s.y, s.x});
	visit[s.y][s.x] = 1;

	while (!q.empty()) {
		tres++;
		int sz = q.size();
		for (int z = 0; z < sz; z++) {
			point t = q.front();
			q.pop();
			for (int i = 0; i < 4; i++) {
				int ty = t.y + dy[i];
				int tx = t.x + dx[i];

				//못가는 조건
				if (ty < 0 || ty >= n || tx < 0 || tx >= n ||
					visit[ty][tx] == 1) continue;
				if (map[ty][tx] > s.sz) continue;

				if (map[ty][tx] != 0 && map[ty][tx] < s.sz) {
					die.push({ ty, tx });
				}

				q.push({ ty, tx});
				visit[ty][tx] = 1;
			}
		}
		if (!die.empty()) {
			eat(die);
			return tres;
		}
	}
	return 0;
}

void level_up() {
	if (s.sz == s.exp) {
		s.sz++;
		s.exp = 0;
	}
}

void simul() {
	while (1) {
		int t = bfs();
		if (t == 0) break;
		time += t;
		level_up();
	}
}

int main() {
	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) {
				s.y = i; s.x = j;
				map[i][j] = 0;
			}
		}
	}
	s.sz = 2;
	s.exp = 0;

	simul();

	cout << time << '\n';
	return 0;
}

 

 

---

 

 

<느낀 점>