백준 2589 : 보물섬 (bfs)

문제

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

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

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

입력

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

출력

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

예제 입력 1 복사

5 7
WLLWWWL
LLLWLLL
LWLWLWW
LWLWLLL
WLLWLWW

예제 출력 1 복사

8

 

• 풀이

 

처음에는 땅 위치 중 2개를 집고 해당 위치마다 bfs를 하는 아래와 같은 코드를 작성했는데 시간초과..

nC2*(n*m) 으로 생각했는데 시간복잡도가 터졌다

#include <vector>
#include <iostream>
#include <algorithm>
#include <queue>

using namespace std;

vector<vector<char>> arr;
vector<vector<int>> visited;
vector<pair<int, int>> treasure;

int pos[4][2] = {{1,  0},
                 {0,  1},
                 {-1, 0},
                 {0,  -1}};

int n, m;

int bfs(int startY, int startX, int targetY, int targetX) {
    queue<pair<int, int>> q;
    q.push({startY, startX});
    visited[startY][startX] = 1;

    while (!q.empty()) {
        auto tmp = q.front();
        q.pop();
        for (int i = 0; i < 4; i++) {
            int dy = tmp.first + pos[i][0];
            int dx = tmp.second + pos[i][1];
            if (dy < 0 || dx < 0 || dy >= n || dx >= m) continue;
            if (visited[dy][dx] != 0 || arr[dy][dx] != 'L') continue;
            q.push({dy,dx});
            visited[dy][dx] = visited[tmp.first][tmp.second]+1;
            if(dy == targetY && dx == targetX) return visited[dy][dx] -1;
        }
    }

    return 0;
}


int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> m;
    arr.resize(n, vector<char>(m));
    for (int i = 0; i < n; i++) {
        string s;
        cin >> s;
        for (int j = 0; j < m; j++) {
            arr[i][j] = s[j];
            if (s[j] == 'L') treasure.push_back({i, j});
        }
    }

    int res = -1;

    for (int i = 0; i < treasure.size(); i++) {
        for (int j = i + 1; j < treasure.size(); j++) {
            visited.clear();
            visited.resize(n, vector<int>(m, 0));
            // 시작지점은 i번째 땅, 목표 지점은 j번째 땅, 갈수 있는지 dfs로 탐색
            int tmp = bfs(treasure[i].first, treasure[i].second, treasure[j].first, treasure[j].second);
            if(tmp != 0)res = max(res,tmp);
        }
    }
    cout << res;
    return 0;
}

 

발상의 전환으로 각 L에서 bfs를 진행하면서 각 칸으로 갈때 최대 거리가 되는걸 찾으면 답이기에 2중 for문으로 모든 L에 대해서 bfs를 돌리는게 더 시간복잡도가 적었다..

 

#include<bits/stdc++.h>

using namespace std;
int n, m, mx, visited[54][54];
const int dy[] = {-1, 0, 1, 0};
const int dx[] = {0,
                  1,
                  0,
                  -1};
char a[54][54];

void bfs(int y, int x) {
    memset(visited, 0, sizeof(visited));
    visited[y][x] = 1;
    queue<pair<int, int>> q;
    q.push({y, x});
    while (q.size()) {
        tie(y, x) = q.front();
        q.pop();
        for (int i = 0; i < 4; i++) {
            int ny = y + dy[i];
            int nx = x + dx[i];
            if (ny < 0 || ny >= n || nx < 0 || nx >= m) continue;
            if (visited[ny][nx]) continue;
            if (a[ny][nx] == 'W')continue;
            visited[ny][nx] = visited[y][x] + 1;
            q.push({ny, nx});
            mx = max(mx, visited[ny][nx]);
        }
    }
    return;
}

int main() {
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> a[i][j];
        }
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (a[i][j] == 'L') bfs(i, j);
        }
    }
    cout << mx - 1 << "\n";
}