BOJ - 17086번 아기 상어 2 (C++)

문제 출처: https://www.acmicpc.net/problem/17086

난이도

Silver 1

접근법

토마토 같은 삼성 역량 문제를 풀어봤으면 쉽게 풀었을 문제! BFS를 이용한다. 대신 빈 칸에서 가장 가까운 상어니깐 빈 칸들만 따로 모아두고 그 좌표를 두고 가까운 아기상어까지 몇 칸이 걸리는지로 짜야한다.
시간 제한이 2초기 때문에 충분!

통과 코드

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

#define INF 987654321

using namespace std;

int arr[51][51];
int dy[8][2] = { {-1,0},{1,0},{0,-1},{0,1},{1,1},{-1,-1},{-1,1},{1,-1} };
bool ch[51][51];
int N, M;

struct info {
	int x, y, cnt;
	info(int a, int b, int c) {
		x = a;
		y = b;
		cnt = c;
	}
};

int bfs(int x, int y) {
	memset(ch, false, sizeof(ch));
	ch[x][y] = true;
	queue<info> q;
	q.push(info(x, y, 0));
	while (!q.empty()) {
		x = q.front().x;
		y = q.front().y;
		int cnt = q.front().cnt;
		q.pop();
		if (arr[x][y] == 1) return cnt;
		for (int k = 0; k < 8; k++) {
			int nx = x + dy[k][0];
			int ny = y + dy[k][1];
			if (nx < 0 || ny < 0 || nx >= N || ny >= M || ch[nx][ny]) continue;
			ch[nx][ny] = true;
			q.push(info(nx, ny, cnt + 1));
		}
	}
	return INF;
}

int main() {
	
	cin >> N >> M;
	vector<pair<int,int>> xy;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			cin >> arr[i][j];
			if (arr[i][j] == 0) xy.push_back({ i,j });
		}
	}
	int res = -1;
	for (int i = 0; i < xy.size(); i++) {
		int x = xy[i].first;
		int y = xy[i].second;

		int n = bfs(x, y);
		res = max(res, n);
	}
	cout << res << "\n";
	return 0;
}