[백준 2589번 C/C++] 보물선

 

[백준 2589번 C/C++] 보물선

 

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

 

2589번: 보물섬

보물섬 지도를 발견한 후크 선장은 보물을 찾아나섰다. 보물섬 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 각 칸은 육지(L)나 바다(W)로 표시되어 있다. 이 지도에서

www.acmicpc.net

---

 

 

해결전략

 

너비우선탐색 BFS

 

---

 

정답 코드

 

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
 
int dirY[4] = { -1, 0, 1, 0 };
int dirX[4] = { 0, -1, 0, 1 };
 
int r, c;
vector<vector<char>> v;
int answer;
 
void BFS(int startY, int startX)
{
	vector<vector<int>> ch(r, vector<int>(c, -1));
	queue<pair<int, int>> Q;
	Q.push({ startY, startX });
	ch[startY][startX] = 0;
 
	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 + dirY[i];
			int nx = x + dirX[i];
 
			if (ny < 0 || r <= ny || nx < 0 || c <= nx || v[ny][nx] == 'W') continue;
 
			if (ch[ny][nx] == -1 && v[ny][nx] == 'L') {
				Q.push({ ny, nx });
				ch[ny][nx] = ch[y][x] + 1;
				answer = max(answer, ch[ny][nx]);
			}
		}
	}
}
 
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
 
	cin >> r >> c;
	v.resize(r, vector<char>(c));
	for(int y = 0; y < r; y++){
		for (int x = 0; x < c; x++) {
			cin >> v[y][x];
		}
	}
 
	for (int y = 0; y < r; y++) {
		for (int x = 0; x < c; x++) {
			if (v[y][x] == 'L')
				BFS(y, x);
		}
	}
 
	cout << answer;
 
	return 0;
}

 

 

---