백준 - 보물섬(2589)

BFS 완전탐색 문제이다.

간단한 골드5 문제이다.

 

#include <iostream>
#include <vector>
#include <string>
#include <queue>
using namespace std;
//보물상자
int dx[4] = { 1, 0, -1, 0 };
int dy[4] = { 0, 1, 0, -1 };
typedef pair<int, int> p;
int BFS(vector<vector<int>> &temp_graph, int start_y, int start_x) {


	queue<p> qq;
	qq.push(p(start_y, start_x));
	int size_y = temp_graph.size();
	int size_x = temp_graph[0].size();
	temp_graph[start_y][start_x] = -1;
	int max_data = 0;
	while (!qq.empty()) {
		int pop_y = qq.front().first;
		int pop_x = qq.front().second;
		qq.pop();

		for (int i = 0; i < 4; i++)
		{
			int new_y = pop_y + dy[i];
			int new_x = pop_x + dx[i];
			if (new_y >= size_y || new_x >= size_x || new_y < 0 || new_x < 0) continue;

			if (temp_graph[new_y][new_x] == 0) {
				temp_graph[new_y][new_x] = temp_graph[pop_y][pop_x] - 1;
				max_data = min(max_data, temp_graph[new_y][new_x]);
				qq.push(p(new_y, new_x));
			}
		}
	}	
	return max_data;
}

int main() {	
	int n, m;
	cin >> n >> m;
	vector<vector<int>> graph(n, vector<int>(m, 0));	
	for (int i = 0; i < n; i++) {
		string temp;
		cin >> temp;

		for (int j = 0; j < m; j++) {
			if (temp[j] == 'W')
				graph[i][j] = 1;
			else
				graph[i][j] = 0;
		}
	}

	int max_data = 0;
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++) {
			if (graph[i][j] == 0) {
				vector<vector<int>> temp_graph = graph;
				max_data = min(max_data, BFS(temp_graph, i, j));
			}
		}

	}
	cout << max_data * -1 - 1;
}

 

BFS는 많이 풀어봐서 금방 풀 수 있었다.

시작지점은 완전탐색을 돌려주면서 BFS를 진행한다.

리턴값을 계속 비교해 가며 가장 거리가 먼 값을 구한다.