백준 16236번 _ 아기 상어

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

16236번: 아기 상어

 

자료형 선언

int map[maxN][maxN];
int sharkSize = 2;
int fishInStomach;
pair<int, int>presentSharkPoisition;
int time;
int n;

 

1. 풀이방법

 

 1) 일반적인 que 이용 bfs모양을 만든다

 2) bfs로 탐색하던중 적합한 점을 찾으면, 그 거리를 저장하고 candidate라는 후보군 vector에 넣어둔다.

 3) 이후의 bfs 탐색은 저장한 거리와 같은 거리의 적합한 점만 찾아 candidate라는 후보군 vector에 추가한다.

 4) bfs 동작이 끝난이후, y점이 제일 작은점, x점이 제일 작은점 기준으로 candidate를 정렬한다.

 3) candidate의 제일 우선순위가 되는값을 꺼내고 상어의 좌표, map의 갱신등을 해준다. 

 

 주의할 점은 내 코드는 상어의 위치를 따로 map에 표시하지않고 presentSharkPoint라는 변수를 만들어 상어의 위치를 저장하고, 계속 갱신하며 풀었다는것에 주의하면 조금 복잡하지만 코드이해가 쉬울거라고 생각한다. 

---

 

2. 코드

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <limits.h>

#define maxN 22

using namespace std;

int map[maxN][maxN];
int sharkSize = 2;
int fishInStomach;
pair<int, int>presentSharkPoisition;
int time;
int n;

class DfsInfo
{
public:
	int y;
	int x;
	int dis;
	DfsInfo(int y_in, int x_in, int dis_in)
		:y(y_in), x(x_in), dis(dis_in)
	{}
};

bool compare(const pair<int, pair<int, int>>& a, const pair<int, pair<int, int>>& b)
{
	if (a.first == b.first)
	{
		return a.second.first < b.second.first;
		if (a.second.first == b.second.first)
			return a.second.second < b.second.second;
	}
	return a.first < b.first;
}

void Input()
{
	cin >> n;
	int value;
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			cin >> value;
			map[i][j] = value;

			if (value == 9)
			{
				presentSharkPoisition = { i, j };
				map[i][j] = 0;
			}
		}
	}
}

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

bool bfs()
{
	bool remainFish = false;
	bool visit[maxN][maxN];
	queue <DfsInfo> que;
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
			visit[i][j] = false;

	que.push(DfsInfo(presentSharkPoisition.first, presentSharkPoisition.second, 0));
	visit[presentSharkPoisition.first][ presentSharkPoisition.second] = true;
	int minDis = INT_MAX;
	vector<pair<int, pair<int, int>>>candidate;

	while (!que.empty())
	{
		int y = que.front().y;
		int x = que.front().x;
		int dis = que.front().dis;
		que.pop();

		//상어가 먹을수 있을때
		if (map[y][x] != 0 && map[y][x] < sharkSize)
		{
			if (minDis < dis)
				break;

			minDis = dis;
			//후보군으로 넣어둠
			candidate.push_back({ dis ,{y, x} });
		}

		//상좌하우 ㄱㄱ
		for (int i = 0; i < 4; i++)
		{
			int ny = y + dy[i];
			int nx = x + dx[i];

			//범위에 성립하고 지나치지 않은 점이여야함
			if (ny >= 0 && nx >= 0 && ny < n && nx < n && !visit[ny][nx])
			{
				//그 점이 지금샤크의 몸땡이보다 크면안됨
				if (map[ny][nx] > sharkSize)
					continue;

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

	//후보군 꺼내기
	if(candidate.size() !=0)
	{
		sort(begin(candidate), end(candidate));
		int y = candidate[0].second.first;
		int x = candidate[0].second.second;
		int dis = candidate[0].first;

		map[y][x] = 0;
		fishInStomach++;
		presentSharkPoisition = { y, x };
		time += dis;
		//몸땡이가 커짐
		if (fishInStomach == sharkSize)
		{
			sharkSize++;
			fishInStomach = 0;
		}
		remainFish = true;
	}

	return remainFish;
}

void solve()
{
	while (1)
	{
		if (!bfs())
			break;
	}
	cout << time;
}

int main()
{
	Input();
	solve();
	return 0;
}

 

---

 

3. 후기

 

 조건이 꽤나 많은 구현문제였다. 구현할게 많다보니 다 구현하고 나서 오류가 있어 디버깅할때 어디서 오류가 나는지 조금 헷갈렸다. 그리고 원래 이런문제는 한번에 조건들을 정리해놓고 푸는게 이상적인데, 중요한 조건만 정리하고 나머지는 디버깅으로 풀어가는 안좋은 코딩스타일이 굳혀져서 잘 고쳐지지가 않는다. 신경써야겠다 ㅠ

 

 아 그리고 나는 처음에 bfs를 구현할때 que에 push할때 visit를 체크하지않고, que를 pop할때 visit를 체크해서 시간초과가 났다. 이 부분을 주의해야겠다.