백준 16236 c++

오랜만에 생각을 많이 해볼만 한 문제였다. 약간 주먹구구식으로 풀다보니 전역변수가 너무 많아지고 코드도 많이 지저분해졌다... 다음 비슷한 문제를 풀면서 정리된 코드를 쓸 수 있도록 하겠다.

처음에는 DFS로 풀어보려다, BFS로 매번 방문을 초기화하면 된다고 생각해 바꿨다.

처음에는 진행방향을 지정해 무조건 처음 만나면 그게 규칙에 맞는 경우라 생각해 pop()을 하려고 했는데 차근차근 해보니 항상 맞지는 않았다. 또한 진행방향도 { {0, 1} ,{-1, 0},{1, 0},{0, -1} }라고 했는데 사실 xy좌표에서는 y가 위일 수록 큰 숫자지만, 컴퓨터좌표에서는 y가 위일 수 록 작은 숫자여서 { {0, -1} ,{-1, 0},{1, 0},{0, 1} } 로 바꾸었다. 그런데 최종 풀이에서는 방향은 의미가 크게 없지만, 바꾸지는 않았다.

결국 최종적으로는 먹을 수 있는 물고기 후보군을 모두 vector에 넣고, 규칙에 따라 정렬한 후 가장 앞에 물고기만 먹고 전부 초기화 하는 방법을 사용했다.

이번엔 진짜로 다른사람 풀이 참고없이 한게 만족스럽다.

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

using namespace std;

vector <vector<int>> space;
vector<pair<int, int>>direction{ {0, -1} ,{-1, 0},{1, 0},{0, 1} };//y좌표의 위아래가 좌표식과 반대임
int N;
int baby_shark_size = 2;
int need = 0;

void input_graph(int* baby_shark_initial_x, int* baby_shark_initial_y)
{
	int i, j;

	cin >> N;
	space.resize(N, vector<int>(N, 0));
	for (i = 0; i < N; i++)
	{
		for (j = 0; j < N; j++)
		{
			cin >> space[i][j];
			if (space[i][j] == 9)
			{
				*baby_shark_initial_x = j;
				*baby_shark_initial_y = i;
			}
		}
	}

	/*for (i = 0; i < N; i++)
	{
		for (j = 0; j < N; j++)
		{
			cout << space[i][j];
		}
		cout << "\n";
	}*/

	return;
}

bool compare(pair<int, int> A, pair<int, int> B)
{
	if (A.second < B.second)//y가 작다는게 더 높이 있다는 뜻
	{
		return true;
	}
	else if(A.second == B.second)
	{
		return A.first < B.first;
	}
	else
	{
		return false;
	}
}

int BFS(int *start_x, int *start_y)
{
	int i, j, count = 0;
	int current_x, current_y, next_x, next_y;
	queue <pair<int, int>> q;//{x좌표, y좌표}
	vector <pair<int, int>> eat;
	vector<vector<bool>> visited(N, vector<bool>(N, false));
	int q_size, d_size = direction.size();

	q.push({ *start_x, *start_y });
	visited[*start_y][*start_x] = true;
	while (!q.empty())
	{
		q_size = q.size();
		for (i = 0; i < q_size; i++)
		{
			current_x = q.front().first;
			current_y = q.front().second;
			q.pop();
			for (j = 0; j < d_size; j++)
			{
				next_x = current_x + direction[j].first;
				next_y = current_y + direction[j].second;
				if ((next_x >= 0 && next_x < N) && (next_y >= 0 && next_y < N) && visited[next_y][next_x] == false)
				{
					if (space[next_y][next_x] == 0)//0인경우
					{
						visited[next_y][next_x] = true;//그냥 통과가능
						q.push({ next_x, next_y });
					}
					else if (space[next_y][next_x] > baby_shark_size)//크기가 큰 물고기는 먹지도 못하고 통과도 불가
					{
						;
					}
					else if (space[next_y][next_x] == baby_shark_size)//크기가 같은 물고기는 못먹지만 통과는 가능
					{
						visited[next_y][next_x] = true;
						q.push({ next_x, next_y });
					}
					else//크기가 작은 물고기는 무조건 먹기
					{
						eat.push_back({ next_x, next_y });
						/*
						need++;
						if (need == baby_shark_size)
						{
							need = 0;
							baby_shark_size++;
						}
						space[*start_y][*start_x] = 0;
						space[next_y][next_x] = 9;
						*start_x = next_x;
						*start_y = next_y;
						return count + 1;
						*/
					}
				}
			}
		}
		if (!eat.empty())//먹을 후보들이 쌓인 경우
		{
			sort(eat.begin(), eat.end(), compare);
			need++;
			if (need == baby_shark_size)
			{
				need = 0;
				baby_shark_size++;
			}
			space[*start_y][*start_x] = 0;
			space[eat.front().second][eat.front().first] = 9;
			*start_x = eat.front().first;
			*start_y = eat.front().second;
			return count + 1;
		}
		count++;
	}

	return 0;
}

void find_answer(int *baby_shark_initial_x, int *baby_shark_initial_y)
{
	//매 물고기 탐색마다 최단거리니까 BFS아닌가
	int time;
	int total = 0;

	while (true)
	{
		time = BFS(baby_shark_initial_x, baby_shark_initial_y);
		/*for (int i = 0; i < N; i++)
		{
			for (int j = 0; j < N; j++)
			{
				cout << space[i][j];
			}
			cout << "\n";
		}
		cout << time << "\n\n";*/
		if (time == 0)
		{
			break;
		}
		total += time;
	}
	cout << total << "\n";

	return;
}

int main(void)
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int baby_shark_initial_x, baby_shark_initial_y;
	
	input_graph(&baby_shark_initial_x, &baby_shark_initial_y);
	find_answer(&baby_shark_initial_x, &baby_shark_initial_y);

	return 0;
}