BOJ 2589. 보물섬

🙇‍♀️[Gold V] 보물섬 - 2589

문제 링크

성능 요약

메모리: 2156 KB, 시간: 164 ms

분류

너비 우선 탐색, 브루트포스 알고리즘, 그래프 이론, 그래프 탐색

제출 일자

2024년 6월 9일 13:31:35

문제 설명

보물섬 지도를 발견한 후크 선장은 보물을 찾아나섰다. 보물섬 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 각 칸은 육지(L)나 바다(W)로 표시되어 있다. 이 지도에서 이동은 상하좌우로 이웃한 육지로만 가능하며, 한 칸 이동하는데 한 시간이 걸린다. 보물은 서로 간에 최단 거리로 이동하는데 있어 가장 긴 시간이 걸리는 육지 두 곳에 나뉘어 묻혀있다. 육지를 나타내는 두 곳 사이를 최단 거리로 이동하려면 같은 곳을 두 번 이상 지나가거나, 멀리 돌아가서는 안 된다.

예를 들어 위와 같이 지도가 주어졌다면 보물은 아래 표시된 두 곳에 묻혀 있게 되고, 이 둘 사이의 최단 거리로 이동하는 시간은 8시간이 된다.

보물 지도가 주어질 때, 보물이 묻혀 있는 두 곳 간의 최단 거리로 이동하는 시간을 구하는 프로그램을 작성하시오.

입력

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

출력

첫째 줄에 보물이 묻혀 있는 두 곳 사이를 최단 거리로 이동하는 시간을 출력한다.

🚀풀이

최단 거리를 구해야하므로 다익스트라를 활용하였다.

bfs를 이차원 배열을 매개변수로 받는 방식으로 구현했다.

// BFS를 이용하여 각 육지 칸에서의 최단 거리를 구하는 함수
int bfs(vector<vector<char>>& grid, int x, int y) 
{
    int n = grid.size();
    int m = grid[0].size();
    vector<vector<bool>> visited(n, vector<bool>(m, false));
    queue<pair<pair<int, int>, int>> q;
    q.push({ {x, y}, 0 });
    visited[x][y] = true;
    int maxDistance = 0;

    while (!q.empty()) 
    {
        int cx = q.front().first.first;
        int cy = q.front().first.second;
        int distance = q.front().second;
        q.pop();
        maxDistance = max(maxDistance, distance);

        for (int i = 0; i < 4; ++i) 
        {
            int nx = cx + dx[i];
            int ny = cy + dy[i];
            if (isValid(nx, ny, n, m) && !visited[nx][ny] && grid[nx][ny] == 'L') 
            {
                q.push({ {nx, ny}, distance + 1 });
                visited[nx][ny] = true;
            }
        }
    }

    return maxDistance;
}

dx, dy와 위치가 grid에 벗어나는지 확인하는 함수도 만들었다.

// 상하좌우 이동을 위한 배열
const int dx[] = { 1, -1, 0, 0 };
const int dy[] = { 0, 0, 1, -1 };

// 지도의 범위를 벗어나는지 확인하는 함수
bool isValid(int x, int y, int n, int m) 
{
    return x >= 0 && x < n && y >= 0 && y < m;
}

최단 거리를 구하기 위해서는 bfs를 육지 한칸당 돌려야하고 그 중 최대값을 구해야한다.

// 보물이 묻혀 있는 두 곳 사이의 최단 거리를 구하는 함수
int shortestTreasureDistance(vector<vector<char>>& grid) 
{
    int n = grid.size();
    int m = grid[0].size();
    int maxDistance = 0;

    for (int i = 0; i < n; ++i) 
    {
        for (int j = 0; j < m; ++j) 
        {
            if (grid[i][j] == 'L') 
            {
                maxDistance = max(maxDistance, bfs(grid, i, j));
            }
        }
    }

    return maxDistance;
}

🚀코드

#define _CRT_SECURE_NO_WARNINGS

#include <stdio.h>
#include <string.h>
#include <ctype.h>
#include<iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <math.h>
#include <climits>
#include <queue>

using namespace std;
// 상하좌우 이동을 위한 배열
const int dx[] = { 1, -1, 0, 0 };
const int dy[] = { 0, 0, 1, -1 };

// 지도의 범위를 벗어나는지 확인하는 함수
bool isValid(int x, int y, int n, int m) 
{
    return x >= 0 && x < n && y >= 0 && y < m;
}

// BFS를 이용하여 각 육지 칸에서의 최단 거리를 구하는 함수
int bfs(vector<vector<char>>& grid, int x, int y) 
{
    int n = grid.size();
    int m = grid[0].size();
    vector<vector<bool>> visited(n, vector<bool>(m, false));
    queue<pair<pair<int, int>, int>> q;
    q.push({ {x, y}, 0 });
    visited[x][y] = true;
    int maxDistance = 0;

    while (!q.empty()) 
    {
        int cx = q.front().first.first;
        int cy = q.front().first.second;
        int distance = q.front().second;
        q.pop();
        maxDistance = max(maxDistance, distance);

        for (int i = 0; i < 4; ++i) 
        {
            int nx = cx + dx[i];
            int ny = cy + dy[i];
            if (isValid(nx, ny, n, m) && !visited[nx][ny] && grid[nx][ny] == 'L') 
            {
                q.push({ {nx, ny}, distance + 1 });
                visited[nx][ny] = true;
            }
        }
    }

    return maxDistance;
}

// 보물이 묻혀 있는 두 곳 사이의 최단 거리를 구하는 함수
int shortestTreasureDistance(vector<vector<char>>& grid) 
{
    int n = grid.size();
    int m = grid[0].size();
    int maxDistance = 0;

    for (int i = 0; i < n; ++i) 
    {
        for (int j = 0; j < m; ++j) 
        {
            if (grid[i][j] == 'L') 
            {
                maxDistance = max(maxDistance, bfs(grid, i, j));
            }
        }
    }

    return maxDistance;
}

int main()
{
	FILE* stream;
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	freopen_s(&stream, "input.txt", "rt", stdin);

    int n, m;
    cin >> n >> m;
    vector<vector<char>> board = vector<vector<char>>(n, vector<char>(m));
    // 예시 입력
    for (int y = 0; y < n; ++y)
    {
        for (int x = 0; x < m; ++x)
        {
            cin >> board[y][x];
        }
    }

    // 최단 거리 출력
    cout << shortestTreasureDistance(board) << endl;  // 출력: 8

	return 0;
}