[백준][bfs] 2589 보물섬 c++ 구현

목차

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

문제

 

문제 구현 방향

다른 bfs문제들과 마찬가지로 초기화 잘 해주고 L인 경우에만 탐색을 해준 뒤 최단 경로들 중에서 가장 큰 값을 출력하면 되는 간단한 문제이다.

 

 

코드 구현

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

int dx[4] = {0, 0, -1, 1};
int dy[4] = { 1, -1, 0, 0 };
char board[100][100] = { 0 };
int visit[100][100] = { 0 };
vector<int> v;  // bfs탐색결과를 넣어주자
int N, M;

int maxd() {  //가장 큰 값 출력해주는 함수
	int max = 0;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			if (visit[i][j] > max)
				max = visit[i][j];
		}
	}
	return max-1;  //visit이 1부터시작했으므로 1빼주어야함
}

int bfs(int start_x, int start_y) {  //기존 bfs방식에 거리를 계속 갱신해 주었다.
	visit[start_y][start_x] = 1;  
	
	queue<pair<int, int>> q;
	q.push({ start_x, start_y });
	while (!q.empty()) {
		int x = q.front().first;
		int y = q.front().second;
		q.pop();
		for (int i = 0; i < 4; i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];
			if (nx < 0 || nx > M - 1 || ny <0 || ny > N - 1)
				continue;
			if (visit[ny][nx] || board[ny][nx] == 'W')
				continue;
			q.push({ nx, ny });
			visit[ny][nx] = visit[y][x]+1;
		}
	}
	return maxd();  	
}

int main() {
	cin >> N >> M;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			cin >> board[i][j];
		}
	}
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			if (board[i][j] == 'L') {  //L인 경우에만 탐색
				memset(visit, 0, sizeof(visit)); //방문 초기화
				v.push_back(bfs(j, i));
			}
			
		}
	}
	cout << *max_element(v.begin(), v.end());
}

//5c3
// 5 4        1 2   (5-3)!