백준 16236 아기 상어

문제

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

코드

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

using namespace std;

int N;
int sharkSize = 2;
int sharkY, sharkX;
int answer = 0;

vector<vector<int>> board;

bool bfs() {
	vector<vector<int>> temp(N, vector<int>(N, 0));
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			if (board[i][j] > sharkSize)
				temp[i][j] = -1;
		}
	}
	queue<pair<int, int>> q;
	q.push({ sharkY,sharkX });

	int dir[4][2] = { {1,0},{-1,0},{0,1},{0,-1} };

	while (!q.empty()) {
		int y = q.front().first;
		int x = q.front().second;
		q.pop();

		for (int i = 0; i < 4; i++) {
			int newY = y + dir[i][0];
			int newX = x + dir[i][1];

			if (newX < 0 || newX >= N || newY < 0 || newY >= N || temp[newY][newX] != 0) continue;

			temp[newY][newX] = temp[y][x] + 1;
			q.push({ newY,newX });
		}
	}

	
	int distans = 1e9;
	bool result = false;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			if (board[i][j] == 0) continue;
			if (board[i][j] < sharkSize) {
				if (temp[i][j] == 0) continue;
				result = true;
				if (distans > temp[i][j]) {
					distans = temp[i][j];
					sharkY = i;
					sharkX = j;
				}
				else if (distans == temp[i][j]) {
					if (i < sharkY) {
						sharkY = i;
						sharkX = j;

					}
					else if (i == sharkY) {
						if (j < sharkX) {
							sharkY = i;
							sharkX = j;
						}
					}
				}
			}
			
		}
	}
	if(distans!=1e9)
		answer += distans;
	return result;
}
int main() {

	cin >> N;
	
	vector<vector<int>> temp(N, vector<int>(N, 0));
	
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			cin >> temp[i][j];
			if (temp[i][j] == 9) {
				temp[i][j] = 0;
				sharkY = i;
				sharkX = j;
			}
		}
	}
	board = temp;
	bool s = true;
	int cnt = 0;
	while (s) {
		board[sharkY][sharkX] = 0;
		s=bfs();
		cnt++;
		if (cnt == sharkSize) {
			sharkSize++;
			cnt = 0;
		}
	}
	cout << answer;
}

풀이

bfs를 활용한 구현 문제입니다.

문제가 살짝 복잡한 만큼 여러가지 풀이법이 있겠지만 저는 상어의 현재 좌표값을 전역변수로 설정하고 bfs를 통해서 상어가 현재 먹을 수 있는 물고기칸까지의 거리를 구한다음에 조건에 맞게 상어의 좌표값을 움직여주면서 답을 구했습니다