[백준/Baekjoon] 2589 보물섬 C++ :: Brute force

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

2589번: 보물섬

---

1. Logic

- 기본 BFS의 형식을 지켜 돌지만 for문을 돌게 되면 원하는 자리가 아닌 제일 처음 나오는 인덱스부터 돌기 때문에 완전탐색을 통해 Land의 모든 부분에서 돌아본 후 가장 최대값을 출력하면 된다.

 

- 모든 인덱스에서 다 돌아봤을때 최대 시간 복잡도는 50 * 50 * 50 * 50 이 되므로 최대 6,250,000이 되어 1억을 넘지 않음으로 풀이 가능하다.

 

 

---

2. Code

#include<bits/stdc++.h>

using namespace std;

vector<vector<char>> vec(51, vector<char> (51, ' '));
vector<vector<int>> length(51, vector<int> (51, 0));
vector<vector<bool>> vis(51, vector<bool> (51, false));

int n, m;

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

int ans = -98754321;

void reset() {
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < m; j++) {
            vis[i][j] = false;
            length[i][j] = 0;
        }
    }
}

void BFS(int yy, int xx) {
    queue<pair<int, int>> q;
    reset();
    q.push({yy, xx});

    vis[yy][xx] = true;

    while(!q.empty()) {
        int y = q.front().first;
        int x = q.front().second;

        q.pop();

        for(int i = 0; i < 4; i++) {
            int ny = y + dy[i];
            int nx = x + dx[i];

            if(nx < 0 || nx >= m || ny < 0 || ny >= n) continue;
            if(vis[ny][nx]) continue;
            if(vec[ny][nx] == 'W') continue;
            
            vis[ny][nx] = true;
            length[ny][nx] = length[y][x] + 1;

            q.push({ny, nx});
            ans = max(ans, length[ny][nx]);
        }
    }
}

int main() {
    cin >> n >> m;

    for(int i = 0; i < n; i++) {
        for(int j = 0; j < m; j++) {
            cin >> vec[i][j];
        }
    }

    for(int i = 0; i < n; i++) {
        for(int j = 0; j < m; j++) {
            if(vec[i][j] == 'W') continue;
            BFS(i, j);
        }
    }

    cout << ans;
}

---

 

 

3. Feedback

- 시간 복잡도를 계산 해보고 풀자

 

728x90