[백준] 16236-아기 상어(C++)

문제링크: https://www.acmicpc.net/problem/16236

16236번: 아기 상어

 

시뮬레이션 문제입니다. 상어가 먹이를 먹으면서 돌아다니는 시간을 출력하는 문제입니다.

 

 

• 1. bfs 를 통해서 도달할 수 있는 위치들의 최단거리를 표시합니다. 
• 2. 배열을 탐색(O(n))하면서 먹을수 있는 먹이이고 최단거리인 먹이를 선택합니다. 
• 3. 먹이를 선택할때에는 위에 있는 먹이, 왼쪽에 있는 먹이가 우선순위를 가지게 됩니다. 
• 4. 1~3번을 반복하며 상어가 이동할 수 있는 최대경로를 계산하고 먹을 먹이가 없는 시점에서의 값을 출력합니다. 

 

예외를 처리해주어야 하는게 상어 위치를 9로 만들어 두시게 되면은 만약 상어의 크기가 9보다 커지게 될때 bfs에서 계속 해당 위치를 탐색하며 무한루프에 빠질 수 있습니다. 그부분 조심하시고, 문제의 조건들을 꼼꼼하게 확인하시면 그렇게 어렵지 않은 문제였습니다.

 

 

정답코드입니다.

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


int n = 0, result = 0;
int sy, sx, ssize = 2, s_ex = 0;
int arr[21][21] = { 0 };
int visited[21][21];
int y_ar[4] = { 0,0,1,-1 };
int x_ar[4] = { 1,-1,0,0 };

void bfs() {

	queue <int> que[2];
	que[0].push(sy);
	que[1].push(sx);
	visited[sy][sx] = 1;
	while (que[0].empty() != 1) {
		int yy = que[0].front();
		int xx = que[1].front();

		que[0].pop(), que[1].pop();

		for (int i = 0; i < 4; i++) {
			int y = y_ar[i] + yy;
			int x = x_ar[i] + xx;

			if(x >=1 && x<=n && y>=1 && y <=n)
				if (visited[y][x] == 0 && arr[y][x] <= ssize) {
					visited[y][x] = visited[yy][xx] + 1;
					que[0].push(y);
					que[1].push(x);

				}
		}

	}
}

bool select_fish() {

	int len = (int)2e9;
	int select_y, select_x;

	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++)
			if (visited[i][j] != 0 && visited[i][j] < len)
				if (ssize > arr[i][j] && arr[i][j] != 0)
					len = visited[i][j], select_y = i, select_x = j;

	if (len != (int)2e9) {

		// 물고기 자리 이동
		arr[sy][sx] = 0;
		sy = select_y;
		sx = select_x;
		arr[sy][sx] = 1000000000;
		result += len - 1;
		s_ex++;
		if (s_ex == ssize)
			s_ex = 0, ssize++;
		return true;
	}
	return false;

}

int main() {
	cin >> n;
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++) {
			cin >> arr[i][j];
			if (arr[i][j] == 9)
				sy = i, sx = j, arr[i][j] = 1000000000;

		}
	while (1) {
		bool jud=false;

		memset(visited, 0, sizeof(visited));
		bfs();

	
		jud = select_fish();
		if (jud == false)
			break;

	}

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