[PS] 아기 상어 / C++ (백준 16236번)

아기상어 (백준 16236번)

 

오랜만에 푸는 생구현 문제(시뮬레이션). BFS로 탐색하면서 문제 조건을 모두 충족시켜야 한다.

처음에 접근을 잘못해서 cost 값을 안 넣고 distance() 함수를 만들어 각 좌표의 거리 차이만큼을 cost로 이용하다가 잠깐 잊고 있던 "자신보다 큰 물고기는 지나가지 못한다는 조건"이 생각나서 2000자 이상 되는 코드에서 꾸역꾸역 cost를 집어넣어 수정했다. 역시 접근을 애초에 잘하거나 코드를 읽기 쉽게 짜지 않으면 디버깅이나 수정할 상황이 올 때 고생이다.

 

bfs 돌리면서 문제 조건만 잘 구현해준다면 n 최댓값도 20이기 때문에 어렵지 않게 풀 수 있다.

pair 남용을 하다가 이후에 구조체를 집어넣은 코드라 queue가 좌표 큐와 cost 큐로 분리되어 있다.. 오랜만에 수기로 발상 생략하고 구현 문제를 암산으로 풀어본 건데 다신 그러지 말아야겠다,, 

#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;

int d[21][21], vi[21][21];
int dir[2][4] = { {-1, 0, 0, 1}, {0, -1, 1, 0} };
int n, shark_size = 2, eat_count = 0;

struct data {
	int y, x, cost;
};

struct data find(int x, int y) {
	queue<pair<int, int> > que;
	queue<int> cost_que;
	vector<struct data> vec;
	que.push(make_pair(y, x));
	cost_que.push(0);

	int stop = 2e9;
	while (1) {
		if (que.empty())break;
		int curx = que.front().second, cury = que.front().first, cost = cost_que.front();
		que.pop();
		cost_que.pop();
		if (cost > stop)break;
		if (d[cury][curx] % 9 != 0) { // 물고기면 vector에 넣고 stop걸기
			if (d[cury][curx] > shark_size)continue; // 나보다 큰 물고기 continue
			else if (d[cury][curx] == shark_size) { // 나랑 똑같은 물고기 지나가거나 stop 걸려있으면 continue
				if (stop != 2e9)continue;
			}
			else { // 나보다 작은 물고기 vec에 넣어서 나중에 비교, stop 걸기, continue
				vec.push_back({ cury, curx, cost });
				stop = cost;
				continue;
			}
		}
		else if (stop != 2e9)continue; // 아님 stop 걸려있는지 확인

		
		for (int i = 0; i < 4; i++) {
			if (cury + dir[0][i] < 0 || cury + dir[0][i] >= n || curx + dir[1][i] < 0 || curx + dir[1][i] >= n)continue;
			if (vi[cury + dir[0][i]][curx + dir[1][i]] == 1)continue;
			vi[cury + dir[0][i]][curx + dir[1][i]] = 1;
			que.push(make_pair(cury + dir[0][i], curx + dir[1][i]));
			cost_que.push(cost + 1);
		}
	}
	if (vec.size()) {
		y = vec[0].y;
		x = vec[0].x;
		int cost = vec[0].cost;
		int vec_size = vec.size();
		for (int i = 1; i < vec_size; i++) {
			if (y == vec[i].y && x > vec[i].x) {
				x = vec[i].x;
				cost = vec[i].cost;
			}
			else if (y > vec[i].y) {
				y = vec[i].y;
				x = vec[i].x;
				cost = vec[i].cost;
			}
		}
		return { y, x, cost };
	}
	return { -1, -1, -1 };
}

int main()
{
	int stx, sty;
	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			scanf("%d", &d[i][j]);
			if (d[i][j] == 9) {
				stx = j;
				sty = i;
			}
		}
	}

	int dap = 0;
	while (1) {
 		struct data pa = find(stx, sty);
 		if (pa.cost == -1)break;
		dap += pa.cost;
		d[sty][stx] = 0;
		d[pa.y][pa.x] = 9;
		eat_count++;
		if (eat_count == shark_size) {
			shark_size++;
			eat_count = 0;
		}
		stx = pa.x;
		sty = pa.y;
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++)vi[i][j] = 0;
		}
	}

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