Notice
Recent Posts
Recent Comments
Link
«   2025/03   »
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
Tags
more
Archives
Today
Total
관리 메뉴

끄적끄적

백준 [2589] 보물섬 본문

코테준비/백준

백준 [2589] 보물섬

alstj_성공 2022. 8. 22. 18:16

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

 

2589번: 보물섬

첫째 줄에는 보물 지도의 세로의 크기와 가로의 크기가 빈칸을 사이에 두고 주어진다. 이어 L과 W로 표시된 보물 지도가 아래의 예와 같이 주어지며, 각 문자 사이에는 빈 칸이 없다. 보물 지도의

www.acmicpc.net

 

#include<iostream>
#include<queue>
#include<algorithm>
#include<cstring>
using namespace std;
char map[51][51];
bool visited[51][51];
queue<pair<pair<int, int>, int>> q;
int dx[4] = { -1,0,0,1 };
int dy[4] = { 0,1,-1,0 };
int N, M, ans = 0;
void bfs(int x, int y) {
visited[x][y] = true;
q.push({ { x, y }, 0 });
while (!q.empty()) {
x = q.front().first.first;
y = q.front().first.second;
int t = q.front().second;
q.pop();
for (int i = 0; i < 4; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
if (map[nx][ny] == 'W') continue;
if (nx >= 0 && nx < N && ny >= 0 && ny < M && !visited[nx][ny]) {
visited[nx][ny] = true;
q.push({ {nx, ny},t + 1 });
ans = max(ans, t + 1);
}
}
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> N >> M;
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
cin >> map[i][j];
}
}
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
if (map[i][j] == 'L') {
memset(visited, false, sizeof(visited));
bfs(i, j);
}
}
}
cout << ans << '\n';
return 0;
}
view raw 2589.cpp hosted with ❤ by GitHub

bfs

" 보물은 서로 간에 최단 거리로 이동하는데 있어 가장 긴 시간이 걸리는 육지 두 곳에 나뉘어 묻혀있다. "

이 말이 무슨말인가 싶었는데, 결국 bfs를 통해서 거리를 탐색했을 때 가장 먼 지점까지의 이동 시간을 구하면 되는 것이었다.

출발지점이 정해지지 않았으므로, 완전탐색 + bfs 를 사용해야한다.

방문여부를 체크해주며 queue에 x,y 좌표와 각 지점까지의 소요시간을 넣어주어 max값을 계산해주었다.

또한 각 좌표에서 출발할 때마다 visited 배열을 초기화해주는 작업이 필요하다

memset -> cstring

max -> algorithm

'코테준비 > 백준' 카테고리의 다른 글

백준 [11559] Puyo Puyo  (0) 2022.08.23
백준 [2644] 촌수계산  (0) 2022.08.23
백준 [1012] 유기농 배추  (0) 2022.08.18
백준 [20166] 문자열 지옥에 빠진 호석  (0) 2022.08.16
백준 [13904] 과제  (0) 2022.08.15