백준 2589번: 보물섬

[문제 링크]

2589번: 보물섬

---

원소가 L인 좌표를 시작점으로 하는 너비 우선 탐색을 수행하면 해당 좌표에서 가장 멀리 떨어진 'L'의 거리를 알 수 있다.

원소가 L인 모든 좌표에 대하여 너비 우선 탐색을 수행하고 그중 최댓값을 출력하면 원하는 결과를 얻을 수 있다.

---

#include <iostream>
#include <cstring>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

struct Pos {
	int y;
	int x;
};

const int INF = 987654321;
int R, C;
char board[50][50];
bool visited[50][50];
int dy[4] = { 0, 0, 1, -1 };
int dx[4] = { 1, -1, 0, 0 };

int bfs(Pos start) {
	queue<pair<Pos, int>> q;
	q.push({ start, 0 });
	visited[start.y][start.x] = true;

	int ret;
	while (!q.empty()) {
		Pos here = q.front().first;
		int dist = q.front().second;
		q.pop();

		ret = dist;
		for (int i = 0; i < 4; i++) {
			Pos there = { here.y + dy[i], here.x + dx[i] };
			int nextDist = dist + 1;

			if (there.y >= 0 && there.y < R && there.x >= 0 && there.x < C)
				if (!visited[there.y][there.x] && board[there.y][there.x] == 'L') {
					visited[there.y][there.x] = true;
					q.push({ there, nextDist });
				}
		}
	}

	return ret;
}

int bfsAll() {
	int ret = 0;

	for (int i = 0; i < R; i++)
		for (int j = 0; j < C; j++) {
			if (board[i][j] == 'L') {
				memset(visited, false, sizeof(visited));
				ret = max(ret, bfs({ i,j }));
			}
		}

	return ret;
}

int main(void) {
	cin >> R >> C;

	for (int i = 0; i < R; i++)
		for (int j = 0; j < C; j++)
			cin >> board[i][j];

	cout << bfsAll() << endl;

	return 0;
}

알고리즘 200일 프로젝트 - 166 day