백준 2589번 - 보물섬 (2회 차)

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

2589번: 보물섬

풀이 과정

 4방향 그래프에서 육지인 곳 중, 최단 거리가 가장 큰 곳의 거리를 구하는 문제이다. 우선 입력을 받고, 모든 노드를 탐색하며 (탐색할 때마다 visited 초기화) visited의 최댓값을 구하며 ret을 최댓값으로 갱신했다.

느낀 점

 기본적인 BFS를 이용한 최단 거리 문제이다.

 

 

#include<bits/stdc++.h>
using namespace std;

const int MAX = 53;
int visited[MAX][MAX], mp[MAX][MAX];
int my[4] = { 1, 0, -1, 0 }, mx[4] = { 0, 1, 0, -1 };
int n, m, ret;
char temp;

//BFS로 탐색하며 최대 visited[][]로 ret갱신
void BFS(int y, int x) {
	queue<pair<int, int>> q;
	visited[y][x] = 1;
	q.push({ y, x });
	while (q.size()) {
		int now_y = q.front().first;
		int now_x = q.front().second;
		for (int i = 0; i < 4; i++) {
			int ny = now_y + my[i];
			int nx = now_x + mx[i];
			if (ny < 0 || ny >= n || nx < 0 || nx >= m || visited[ny][nx] || !mp[ny][nx])continue;
			visited[ny][nx] = visited[now_y][now_x] + 1;
			ret = max(ret, visited[ny][nx] - 1);
			q.push({ ny, nx });
		}
		q.pop();
	}
	return;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	//입력
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> temp;
			if (temp == 'W') mp[i][j] = 0;
			else mp[i][j] = 1;
		}
	}

	//모든 노드 탐색
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (!mp[i][j]) continue; //육지일 경우에만 탐색
			fill(&visited[0][0], &visited[0][0] + MAX * MAX, 0);
			BFS(i, j); //BFS 탐색
		}
	}
	
	//출력
	cout << ret;

	return 0;
}