2589 : 보물섬 - BFS

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

2589번: 보물섬

문제요약

최단거리가 가장 먼 육지의 두 곳에 보물심기

 

난이도

Gold 5

---

풀이 포인트

• BFS를 실행하면, 한 칸씩 움직일 때마다 최단거리가 갱신됨
  • 즉, 도착 지점 과 출발지점 쌍이 계속 나오기 때문에 2쌍을 뽑아서 돌릴 필요가 없다.
• BFS 

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;
}

---

REVIEW

 

우선 BFS는 아직 소스코드를 안 보고 칠 만큼 익숙해지지 못했다는 것 반성.

시간 초과가 나자마자 모범 답안으로 달려간 것도 약간 반성.

 

BFS로 탐색했을 때 왜 최단 거리가 되는 건지 아직 탐구를 제대로 하지 못했으므로 공부하기.

---

CODE

#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";
}

// 일단 입력받아 표시하기
// 두 군데 뽑기 
// 최단거리 구하기 , max 갱신하기

// 시간 초과 코드

#include <bits/stdc++.h>
using namespace std;

int n, m, a[51][51], visited[51][51];
string s;

vector<pair<int, int>> LPos;

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

int bfs(int sx, int sy, int ex, int ey){

    queue<pair<int, int>> q;

    visited[sx][sy] = 1;
    q.push({sx,sy});

    while(q.size()){
        tie(sx,sy) = q.front();
        q.pop();

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

            if(nx < 0 || nx >= n || ny < 0 || ny >= m || a[nx][ny] == 0) continue;
            if(visited[nx][ny]) continue;

            if (sx == ex && sy == ey)
            {
                return visited[sx][sy];
            }

            visited[nx][ny] = visited[sx][sy] + 1;
            q.push({nx, ny});
        }
    }

    return -1;
}


int main(){

    ios_base::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++){
            if(s[0] == 'W') a[i][j] = 0;
            if(s[0] == 'L') {
                a[i][j] = 1;
                LPos.push_back({i,j});
            }
            s.erase(0,1);           
        }
    }

    int mxd = 0;

    for(int i = 0; i < LPos.size()-1; i++){
        for(int j = i ; j < LPos.size(); j++){

            memset(visited, false, sizeof(visited));


            //cout << "시작 좌표는 (" << LPos[i].first << "," << LPos[i].second <<") 이고 종착 좌표는 (" <<   LPos[j].first << "," << LPos[j].second <<")\n";
            int k = bfs(LPos[i].first, LPos[i].second, LPos[j].first, LPos[j].second);
            mxd = max(k, mxd);
        }
    }

    cout << mxd;

}