백준 2589 보물섬 풀이

사용언어

Visual studio 2019 C++

문제 간단요약

L이 가장 멀리 떨어져있는 거리 구하기!

생각하기

bfs(너비우선탐색) 알고리즘 사용하기 시작과 도착하는 점이 따로 없어서 Brute Force(완전탐색) 알고리즘 사용

[2589 풀이]

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <queue>
using namespace std;
int N, M;
string wl[50];
int visited[50][50];
vector<pair<int, int>> v;

int gogoA[4] = { 0,1,0,-1 };
int gogoB[4] = { 1,0,-1,0 };

void bfs(pair<int, int> p) {
	queue<pair<int, int>> q;
	q.push(p);
	visited[p.first][p.second] = 1; // 첫 시작라인 1

	while (!q.empty()) {
		pair<int, int> t = q.front();
		q.pop();

		for (int i = 0; i < 4; i++) {
			int A = t.first + gogoA[i];
			int B = t.second + gogoB[i];
			if (A >= 0 && A < N && B >= 0 && B < M) {
				if (!visited[A][B] && wl[A][B] == 'L') {
					q.push(make_pair(A, B));
					visited[A][B] = visited[t.first][t.second] + 1;
				}
			}
		}
	}
}

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

	for (int i = 0; i < N; i++) {
		cin >> wl[i];
		for (int j = 0; j < M; j++) {
			if (wl[i][j] == 'L')
				v.push_back(make_pair(i, j)); 
				// 땅인 경우의 수를 vector에 넣는다
		}
	}
	int cnt = 0;
	for (int i = 0; i < v.size(); i++) {
		memset(visited, false, sizeof(visited)); // 각각할때마다 초기화
		bfs(v[i]);
		for (int i = 0; i < N; i++)
			for (int j = 0; j < M; j++)
				cnt = max(cnt, visited[i][j] - 1); 
				// 처음시작할때 1을 더 더해서 1 빼기
	}
	cout << cnt << "\n";
}