[BOJ] 17086 아기 상어 2 / C++

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

17086번: 아기 상어 2

 

#include <stdio.h>
#include <vector>
#include <queue>

using namespace std;

int N, M; // 2 <= N, M <= 50
int map[60][60]; // 0: 빈칸, 1: 아기 상어
int visited[60][60];

int dr[8] = { -1,-1,-1,0,1,1,1,0 };
int dc[8] = { -1,0,1,1,1,0,-1,-1 };

struct st {
	int r, c, t;
};

queue <st> q;
vector <pair<int, int> >blank_spot;
int answer = 0;

void clear_visited()
{
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < M; j++)
		{
			visited[i][j] = 0;
		}
	}
}

void input()
{
	scanf("%d %d", &N, &M);
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < M; j++)
		{
			scanf("%1d", &map[i][j]);
			if (map[i][j] == 0) blank_spot.push_back(make_pair(i, j));
		}
	}
}

int getDistance(int r, int c)
{
	if (!visited[r][c])
	{
		visited[r][c] = 1;
	}
	q.push({ r,c,0 });

	while (!q.empty())
	{
		struct st data = q.front();
		int cur_r = data.r;
		int cur_c = data.c;
		int cur_t = data.t;
		q.pop();
		if (map[cur_r][cur_c] == 1) return cur_t;

		for (int k = 0; k < 8; k++)
		{
			int nr = cur_r + dr[k];
			int nc = cur_c + dc[k];

			if (nr < 0 || nr >= N || nc < 0 || nc >= M || visited[nr][nc]) continue;
			visited[nr][nc] = 1;
			q.push({ nr,nc, cur_t + 1 });
		}
	}
	return 0;
}

void solve()
{
	for (int i = 0; i < blank_spot.size(); i++)
	{
		clear_visited();
		int r = blank_spot[i].first;
		int c = blank_spot[i].second;

		int dist = getDistance(r, c);
		while (!q.empty()) q.pop();
		//printf("[%d] dist = %d, size = %d\n", i, dist, q.size());
		if (dist > answer) answer = dist;
	}
}

int main(void)
{
	input();
	solve();
	printf("%d\n", answer);
	return 0;
}

 

문제를 잘 읽자!!

 

1. N x M의 입력을 받으며 빈 칸의 좌표들을 vector에 저장함

2. vector의 각 원소에 대해 BFS를 이용하여 이동한 칸을 세고, 이동한 칸의 최소값을 얻기 위해서 아기상어를 만나면 그때까지 이동한 칸의 값을 return 한다.