[C++] 백준 2589번 보물섬

그래프 탐색 문제.

오랜만에 풀어보는 알고리즘 문제라 그런지 머리가 잘 안 돌아갔지만 

그래프 탐색이란 것을 알고 쉽게 풀 수 있었다.

 

문제풀이

땅 - 땅으로 이동하는 거리중 가장 긴 거리를 찾으면 된다.

돌아가면 안되고 최단거리 기준이므로 DFS는 안되고 BFS로 탐색해야한다.

이 기준대로만 구현하면 쉽게 풀 수 있다.

/*
* 백준 2589번 보물섬
* https://www.acmicpc.net/problem/2589
* 그래프 탐색 이론 - 너비 우선 탐색, 브루트 포스
*/
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

int height, width;
char board[51][51];
bool visit[51][51];
vector<pair<int, int>> visitVec;
vector<pair<int, int>> landVec;
pair<int, int> directions[4] = {
    {-1, 0},
    {0, 1},
    {1, 0},
    {0, -1}
};
int ans;

void bfs(int r, int c) {
    queue<pair<int, pair<int, int>>> q;
    q.push({ 0, {r, c} });
    visit[r][c] = true;
    visitVec.push_back({ r, c });
    while (!q.empty()) {
        int curR = q.front().second.first;
        int curC = q.front().second.second;
        int curCost = q.front().first;
        q.pop();
        ans = max(ans, curCost);

        for (pair<int, int> p : directions) {
            int nxtR = curR + p.first;
            int nxtC = curC + p.second;
            int nxtCost = curCost + 1;

            if (nxtR < 1 || nxtR > height || nxtC < 1 || nxtC > width || board[nxtR][nxtC] != 'L' ||
                visit[nxtR][nxtC]) { continue; }
            visit[nxtR][nxtC] = true;
            visitVec.push_back({ nxtR, nxtC });
            q.push({ nxtCost, {nxtR, nxtC} });
        }
    }

}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> height >> width;

    for (int i = 1; i <= height; i++) {
        for (int j = 1; j <= width; j++) {
            cin >> board[i][j];
            if (board[i][j] == 'L') {
                landVec.push_back({ i, j });
            }
        }
    }

    for (pair<int, int> p : landVec) {
        visitVec.clear();

        bfs(p.first, p.second);

        for (pair<int, int> p : visitVec) {
            visit[p.first][p.second] = false;
        }
    }

    cout << ans;

    return 0;
}

나같은 경우에는 땅의 좌표들을 landVec에 저장해두고

landVec에 담겨있는 좌표들에서만 bfs를 시작했다.

그리고 visitVec을 활용해서 vist 배열을 초기화했다.

 

처음에 visit 배열을 초기화하는 시간을 줄이려고 visit배열을 visit[51][51][51][51]로 만들었었다.

[시작좌표R][시작좌표C][다음좌표R][다음좌표C]의 형태로 확인하는 것이다.

근데 메모리도 많이 잡아먹고 시간도 별 차이 없어서 본문과 같은 코드로 수정했다.

 

GitHub - kimyunseok/cpp: C++로 코딩한 기록들을 담은 Repository입니다.

코드 전문은 위에서 확인 가능하다.