[16236번 아기 상어] - C++

[16236번 아기 상어]
https://www.acmicpc.net/problem/16236

[19236번 청소년 상어]
https://www.acmicpc.net/problem/19236
https://velog.io/@statco19/boj-19236

[19237번 어른 상어]
https://www.acmicpc.net/problem/19237
https://velog.io/@statco19/boj-19237

아기 - 청소년 - 어른 상어 시리즈의 첫 번째 문제다.

최단거리를 찾는 BFS를 이용한 비교적 간단한 구현 문제였다. 중간에 segmentation fault 에러와 참조자 문법에 익숙하지 않았던 점이 구현을 하는 데 꽤나 긴 시간을 소모하게 만들었다.

풀이

이 문제에서 깜빡하기 쉬운 부분은 입력 받을 때, 물고기의 시작 위치도 빈 칸으로 간주해야 한다는 것이다. 따라서 9가 입력이 되면, 현재 위치로 저장하되 그 칸은 다시 0으로 만들어 줘야 한다.

1.

상어의 현재 위치에서 BFS를 사용하여 자신보다 크기가 작은 물고기를 찾는다. BFS를 이용하여 찾았기 때문에 거리는 최소가 보장된다.

2.

거리가 최소인 물고기가 여러 마리일 경우, 물고기의 위치를 저장해둔 vector를 순회하며 조건에 맞는 물고기의 좌표를 구한다. 좌표에 해당하는 구역을 0으로 만들고, 그 물고기를 먹은 것으로 처리한다.

3.

먹은 물고기의 수가 현재 물고기의 크기와 같아질 때, 물고기 크기를 하나 증가시키고, 먹은 물고기의 수를 다시 0으로 초기화한다.

4.

먹을 수 있는 물고기가 존재하지 않아 초기의 최단 거리 값인 -1을 리턴하게 되면, 모든 것을 멈추고 현재까지 움직인 거리를 출력한다.

C++ 코드

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
#include <vector>
#include <utility>  // pair
#include <tuple>
#include <stack>
#define ll long long
#define INF 1e9
using namespace std;

int ans;
int n;
int sharkSize = 2;
int eatenFish = 0;  // # of fish eaten
int map[21][21];
int visited[21][21];
int dr[] = {-1,0,1,0};
int dc[] = {0,1,0,-1};
int r,c;

int fishDist(int& r, int& c) {
	int dist = 0;
	int found = 0;

	queue<pair<int,int> > q;
	vector<pair<int,int> > arr;

	q.push(make_pair(r,c));

	while(!q.empty() && !found) {
		dist++;
		int size = q.size();

		for(int k=0;k<size;++k) {
			pair<int,int> p = q.front();
			q.pop();

			int i,j;
			i = p.first;
			j = p.second;
			visited[i][j] = 1;

			for(int d=0;d<4;++d) {
				int ni,nj;
				ni = i+dr[d];
				nj = j+dc[d];

				if(!(1 <= ni && ni <= n && 1 <= nj && nj <= n)) {
					continue;
				}

				if(!visited[ni][nj]) {
					visited[ni][nj] = 1;
					if(map[ni][nj] == 0) {
						q.push(make_pair(ni,nj));
					}
					else if(map[ni][nj] <= sharkSize) {
						if(map[ni][nj] < sharkSize) {  // fish to eat found
							arr.push_back(make_pair(ni,nj));
							if(!found) {
								found = 1;
							}
						} else {
							q.push(make_pair(ni,nj));
						}
					}
				}
			}
		}
	}

	if(arr.size() == 0) {
		return -1;
	}

	int row,col;
	row=987654321;
	col=987654321;

	for(int i=0;i<arr.size();++i) {
		pair<int,int>& p = arr[i];
		int R,C;
		R = p.first;
		C = p.second;
		if(R < row) {
			row = R;
			col = C;
		} else if(R == row) {
			col = min(C,col);
		}
	}

	map[row][col] = 0;  // eat fish
	r = row;
	c = col;
	if(++eatenFish == sharkSize) {
		sharkSize++;
		eatenFish = 0;
	}

	return dist;
}

void sol() {
	
	while(true) {
		memset(visited,0,sizeof(visited));
		int dist;
		dist = fishDist(r,c);
		
		if(dist == -1) {  // no fish to eat
			break;
		}
		ans += dist;
	}

	return;
}

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

	scanf("%d", &n);

	for(int i=1;i<=n;++i) {
		for(int j=1;j<=n;++j) {
			scanf("%d", &map[i][j]);
			if(map[i][j] == 9) {  // shark position
				r = i;
				c = j;
				map[i][j] = 0;
			}
		}
	}

	sol();

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

실행 결과