[브루트 포스 / BOJ 2589 / C++] 보물섬

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

2589번: 보물섬

1) 모든 L에 대해 bfs를 해준다.
1-1) 이때, 가중치로 나온 더해진 값들을 확인해나가며 res를 갱신한다.
2) res-1를 출력한다.

이 문제는 bfs 개념을 알고 있다면 쉽게 풀린다!

 

L를 만날때마다 bfs를 수행해보자. 그렇다면, 

 

(0,0)에서 시작할 경우

위 그림에서 파란색으로 색칠한칸은 W, 빨강색 칸은 L이다. 이때 (0,0)(빨강색 숫자 1)에서 bfs를 시작할 경우, 가중치 1를 더한다 생각한다면, 위의 그림과 같이 보인다.

 

(1,0)에서 bfs를 시작할 경우

이번에는 (1,0)에서 bfs를 시작했다. (0,0)에서 시작할 경우와 차이를 보인다. 즉, 임의의 2칸의 최단 거리는 어디서 시작하냐에 따라 다르다. 그렇기 때문에 모든 L에 대해 bfs를 해주고, 그 중 가중치를 더해나간 값중 가장 큰 값을 선택한다!

 

결국은 그냥 모든 L에 대해 bfs를 구해주면 해결되는 쉬운문제!

 

(나는 처음에 임의의 땅 2개를 골라서(조합으로) bfs를 돌려줬는데 시간복잡도가 오바됐다.. 그런데 더 단순한 방법이 있었다.)

#include <bits/stdc++.h>

using namespace std;

int N, M, res;
int vis[54][54];
char bd[54][54];
string s;

int dy[4] = {0, -1, 0, 1};
int dx[4] = {1, 0, -1, 0};

void bfs(int i, int j){
    
    memset(vis, 0, sizeof(vis));
    
    queue<pair<int,int>> Q;
    
    Q.push({i,j}); // Q삽입
    vis[i][j] = 1; // 방문표시
    
    
    while(!Q.empty()){
        pair<int, int> cur = Q.front(); Q.pop();
        
        for(int dir = 0 ; dir < 4 ; dir++){
            int ny = cur.first + dy[dir];
            int nx = cur.second + dx[dir];
            
            if(ny >= N || nx >= M || ny < 0 || nx < 0) continue;
            if(bd[ny][nx]=='W' || vis[ny][nx]!=0) continue; // 방문했거나 물이면 pass
            
            Q.push({ny, nx});
            vis[ny][nx] = vis[cur.first][cur.second] + 1;
            res = max(res, vis[ny][nx]);
            
        }
    }
    
}


int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    cin >> N >> M;

    for(int i = 0 ; i < N ; i++){
        cin >> s;
        for(int j = 0 ; j < M ; j++){
            bd[i][j] = s[j];
        }
    } // 입력 받기
    
    for(int i = 0 ; i < N ; i++){
        for(int j = 0 ; j < M ; j++){
            if(bd[i][j]=='L') bfs(i, j);
        }
    } // 모든 L에 대해 bfs 수행
    
    
    cout << res-1;
}