[백준] 보물섬 (2589/C++)

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

2589번: 보물섬

코드 설명

BFS 기본문제 입니다.

BFS를 반복적으로 사용하여 거리가 가장 긴 구간을 완전탐색하여 구하는 문제였습니다.

가장 긴 거리를 재기위해 result라는 또하나의 map을 만들어주어서 거리를 기록하였습니다.

 

 

코드

#include<iostream>
#include<cstring>
#include<vector>
#include<queue>
using namespace std;
int N, M;
char map[51][51];
bool visited[51][51];
int dx[] = { -1,1,0,0 };
int dy[] = { 0,0,1,-1 };
int result[51][51];
int maxx;
void bfs(int y, int x) {
	queue<pair<int, int>> q;
	q.push({ y,x });
	visited[y][x] = true;

	while (!q.empty()) {
		int y = q.front().first;
		int x = q.front().second;
		q.pop();

		for (int i = 0; i < 4; i++) {
			int ny = y + dy[i];
			int nx = x + dx[i];
			if (ny < 0 || nx < 0 || ny >= N || nx >= M) continue;
			if (!visited[ny][nx] && map[ny][nx]=='L') {
				q.push({ ny,nx });
				visited[ny][nx] = true;
				result[ny][nx] = result[y][x] + 1;
			}

		}



	}
	
	for (int y = 0; y < N; y++) {
		for (int x = 0; x < M; x++) {
			if (maxx < result[y][x]) maxx = result[y][x];

		}
	}

}
int main() {
	cin >> N >> M;

	for (int y = 0; y < N; y++) {
		for (int x = 0; x < M; x++) {
			cin >> map[y][x];


		}


	}
	for (int y = 0; y < N; y++) {
		for (int x = 0; x < M; x++) {
			if (map[y][x] == 'L'){
				memset(result, 0, sizeof(result));
				memset(visited, false , sizeof(visited));
				bfs(y, x);
			}
		}
	}
	cout << maxx;
	return 0;
}