[Baekjoon(백준)][2589번] 보물섬(C++)

안녕하세요! 오늘은 코딩테스트 문제 중 하나인 "보물섬" 문제를 해결하는 방법에 대해 설명하려고 합니다. 이 문제에서는주어진 지도에서 최대한 먼 두 육지 간의 최단 거리를 찾는 문제입니다. 문제를 해결하는 과정과 코드를 자세히 알아보겠습니다.

문제링크:

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

2589번: 보물섬

문제 개요

"보물섬" 문제는 주어진 지도에서 최대한 먼 두 육지 간의 최단 거리를 찾는 문제입니다. 지도는 '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" 알고리즘을 이용하여 모든 육지 칸에서 최대 거리를 찾는 방식으로 문제를 해결할 수 있습니다. 이 방법은 모든 가능한 경로를 고려하여 최적의 해를 찾는 데 효과적입니다.