Beakjoon 2589 보물섬

09 Feb 2021 in Algorithm

문제 링크 : https://www.acmicpc.net/problem/2589

나의 풀이

bfs를 사용하면 시작 지점부터 연결되어있는 모든 육지까지의 시간을 구할 수 있다. 시간이 오래 걸리는 육지에 보물이 있기 때문에 모든 육지를 각각 bfs의 시작 지점으로 하여 가장 큰 값을 찾으면 그 값이 정답이 된다.

풀이 코드 : 2589 보물섬

#include <iostream>
#include <vector>
#include <cmath>
#include <queue>
using namespace std;

vector<vector<int>> map;

int x_[] = {1, -1, 0, 0};
int y_[] = {0, 0, 1, -1};

int bfs(int start_y, int start_x){
    queue<pair<int, int>> q;
    q.push(make_pair(start_x, start_y));
    pair<int, int> xy;
    int max_ = 0;
    map[start_y][start_x] = 1;
    while(!q.empty()){
        xy = q.front();
        q.pop();
        int x = xy.first;
        int y = xy.second;
        if(max_ < map[y][x]) max_ = map[y][x];
        for(int i=0;i<4;i++){
            int curr_x = x_[i] + x;
            int curr_y = y_[i] + y;
            if(0 <= curr_x && curr_x < map[0].size() && 0<=curr_y && curr_y < map.size() && map[curr_y][curr_x] == 0 ){
                map[curr_y][curr_x] =  map[y][x] + 1;
                q.push(make_pair(curr_x, curr_y));
            } 
        }
    }
    return max_;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int w, h;
    char c;
    cin>>h>>w;
    map.resize(h);
    for(int i=0;i<h;i++){
        map[i].resize(w);
        for(int j=0;j<w;j++){
            cin>>c;
            if(c == 'L'){
                map[i][j] = 0;
            }
            else{
                map[i][j] = -1;
            }
        }
    }
    vector<vector<int>> map_temp = map;
    vector<pair<int, int>> end_point;
    int answer = 0;

    for(int i=0;i<h;i++){
        for(int j=0;j<w;j++){
            if(map[i][j] == 0){
                int res = bfs(i, j);
                if(answer < res) answer = res;
                map = map_temp;
            }
        }
    }
    
    cout<<answer-1;
}

채점결과