끄적끄적
백준 [2589] 보물섬 본문
출처 : https://www.acmicpc.net/problem/2589
2589번: 보물섬
첫째 줄에는 보물 지도의 세로의 크기와 가로의 크기가 빈칸을 사이에 두고 주어진다. 이어 L과 W로 표시된 보물 지도가 아래의 예와 같이 주어지며, 각 문자 사이에는 빈 칸이 없다. 보물 지도의
www.acmicpc.net
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#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; | |
} |
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 |