백준 2589번 : 보물섬 / C++
2023. 3. 23. 15:25ㆍ개인공부/코딩테스트
https://www.acmicpc.net/problem/2589
2589번: 보물섬
보물섬 지도를 발견한 후크 선장은 보물을 찾아나섰다. 보물섬 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 각 칸은 육지(L)나 바다(W)로 표시되어 있다. 이 지도에서
www.acmicpc.net
BFS로 모든경로를 탐색하여 문제를 해결했다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
|
#include <iostream>
#include <queue>
using namespace std;
int arr[50][50]{};
int N, M;
int ans = 0;
enum
{
WATER,
LAND,
};
void BFS(int row, int col)
{
queue<pair<int, int>> Q;
Q.push(make_pair(row, col));
bool Visited[50][50]{};
Visited[row][col] = true;
int Max = -1;
while (!Q.empty())
{
queue<pair<int, int>> tmp;
while (!Q.empty()) {
int NowRow = Q.front().first;
int NowCol = Q.front().second;
// up row-1
if (NowRow > 0 && Visited[NowRow - 1][NowCol] == false && arr[NowRow - 1][NowCol] == LAND) {
Visited[NowRow - 1][NowCol] = true;
tmp.push(make_pair(NowRow - 1, NowCol));
}
// down row+1
if (NowRow + 1 < N && Visited[NowRow + 1][NowCol] == false && arr[NowRow + 1][NowCol] == LAND) {
Visited[NowRow + 1][NowCol] = true;
tmp.push(make_pair(NowRow + 1, NowCol));
}
// left col-1
if (NowCol > 0 && Visited[NowRow][NowCol - 1] == false && arr[NowRow][NowCol - 1] == LAND) {
Visited[NowRow][NowCol - 1] = true;
tmp.push(make_pair(NowRow, NowCol - 1));
}
// right col+1
if (NowCol + 1 < M && Visited[NowRow][NowCol + 1] == false && arr[NowRow][NowCol + 1] == LAND) {
Visited[NowRow][NowCol + 1] = true;
tmp.push(make_pair(NowRow, NowCol + 1));
}
Q.pop();
}
Q = tmp;
++Max;
}
if (Max > ans)
ans = Max;
}
int main()
{
cin >> N >> M; // row , col
for (int i = 0; i < N; ++i) {
string str;
cin >> str;
for (int j = 0; j < M; ++j) {
if (str[j] == 'W')// 바다
arr[i][j] = WATER;
else
arr[i][j] = LAND;
}
}
for (int i = 0; i < N; ++i){
for (int j = 0; j < M; ++j){
if (arr[i][j] == LAND)
BFS(i, j);
}
}
cout << ans;
}
|
cs |
'개인공부 > 코딩테스트' 카테고리의 다른 글
| 백준 2638번 : 치즈 / C++ (0) | 2023.03.24 |
|---|---|
| 백준 2573번: 빙산 / C++ (1) | 2023.03.24 |
| 백준 11657번 : 타임머신 / C++ (0) | 2023.03.22 |
| 백준 9370번 : 미확인 도착지 / C++ (0) | 2023.03.21 |
| 백준 1504번 : 특정한 최단 경로 / C++ (0) | 2023.03.20 |