코딩테스트/백준
[Baekjoon(백준)][2589번] 보물섬(C++)
유니얼
2024. 2. 6. 00:21
728x90
안녕하세요! 오늘은 코딩테스트 문제 중 하나인 "보물섬" 문제를 해결하는 방법에 대해 설명하려고 합니다. 이 문제에서는주어진 지도에서 최대한 먼 두 육지 간의 최단 거리를 찾는 문제입니다. 문제를 해결하는 과정과 코드를 자세히 알아보겠습니다.
문제링크:
https://www.acmicpc.net/problem/2589
2589번: 보물섬
첫째 줄에는 보물 지도의 세로의 크기와 가로의 크기가 빈칸을 사이에 두고 주어진다. 이어 L과 W로 표시된 보물 지도가 아래의 예와 같이 주어지며, 각 문자 사이에는 빈 칸이 없다. 보물 지도의
www.acmicpc.net
문제 개요
"보물섬" 문제는 주어진 지도에서 최대한 먼 두 육지 간의 최단 거리를 찾는 문제입니다. 지도는 'L'(육지)과 'W'(바다)로 구성되어 있으며, 상하좌우로만 이동할 수 있습니다.
해결 전략
이 문제를 해결하기 위해 BFS(너비 우선 탐색) 알고리즘을 사용합니다. 모든 육지 칸에서 BFS를 수행하여 가장 먼 거리를 찾습니다. BFS는 시작 지점으로부터 모든 가능한 지점까지의 최단 거리를 찾을 때 자주 사용되는 알고리즘입니다.
코드 구현
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
int m, n, ret;
char maps[52][52];
int visited[52][52];
int dy[4] = { -1,0,1,0 };
int dx[4] = { 0,1,0,-1 };
// BFS 함수
void bfs(int y, int x) {
// 방문 배열 초기화
fill(&visited[0][0], &visited[0][0] + 52 * 52, false);
visited[y][x] = 1;
queue<pair<int, int>> q;
q.push({ y,x });
while (!q.empty())
{
pair<int, int> cur = q.front();
q.pop();
for (int i = 0; i < 4; i++) {
int ny = cur.first + dy[i];
int nx = cur.second + dx[i];
// 지도 범위를 벗어나거나, 이미 방문했거나, 바다인 경우 스킵
if (ny < 0 || nx < 0 || ny >= m || nx >= n || visited[ny][nx] || maps[ny][nx] == 'W') continue;
visited[ny][nx] = 1 + visited[cur.first][cur.second];
q.push({ ny,nx });
ret = max(ret, visited[ny][nx]);
}
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >> m >> n;
for (int i = 0; i < m; i++) {
string temp;
cin >> temp;
for (int j = 0; j < n; j++) {
maps[i][j] = temp[j];
}
}
// 모든 육지 칸에서 BFS 수행
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (maps[i][j] == 'L') bfs(i, j);
}
}
// 결과 출력 (시작점 포함하여 계산했으므로 -1)
cout << ret - 1 << "\n";
}
코드 설명
- 지도의 모든 육지 칸에서 BFS를 시작하여, 각 시작점에서 가장 먼 거리를 찾습니다.
- visited 배열을 사용하여 이미 방문한 지점과 거리를 기록합니다.
- 최대 거리 ret를 갱신하여, 모든 BFS 탐색이 끝난 후 최대 거리를 출력합니다.
결론
"BFS" 알고리즘을 이용하여 모든 육지 칸에서 최대 거리를 찾는 방식으로 문제를 해결할 수 있습니다. 이 방법은 모든 가능한 경로를 고려하여 최적의 해를 찾는 데 효과적입니다.
반응형