백준 2589 - 보물섬

C++

2589 번 - 보물섬

문제

보물섬 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 각 칸은 육지(L)나 바다(W)로 표시되어 있다.
이 지도에서 이동은 상하좌우로 이웃한 육지로만 가능하며, 한 칸 이동하는데 한 시간이 걸린다.
보물은 서로 간에 최단 거리로 이동하는데 있어 가장 긴 시간이 걸리는 육지 두 곳에 나뉘어 묻혀있다.
보물 지도가 주어질 때, 보물이 묻혀 있는 두 곳 간의 최단 거리로 이동하는 시간 중 가장 큰 값을 구하는 프로그램을 작성하시오. 문제 출처

접근 방법

1. 땅이라고 인식되는 좌표를 저장합니다
2. 저장한 좌표를 하나씩 꺼내가며 BFS 함수의 인자로 넣어, 모든 땅을 검사합니다.
3. 매개변수로 받은 좌표에서 시작해, 갈 수 있는 최단 거리를 구합니다.
4. biggest()을 통해 그 최단거리 중 가장 가장 긴 시간이 걸리는 육지 두곳의 거리를 구합니다.
5. init()을 통해 앞선 BFS()에서 사용한 visited와 road를 초기화 하고 다음 좌표를 받아 앞선 3,4번 과정을 반복합니다.

코드

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

using namespace std;

int n, m, result;
char graph[50][50];             //초기 지도
bool visited[50][50];           //방문 여부를 확인하기 위한 배열
int road[50][50];               //최단 거리를 저장하기 위한 배열
queue<pair<int, int>> land;     //땅 좌표만 모아놓은 queue

int goy[4] = { -1, 1, 0, 0 };
int gox[4] = { 0, 0, -1, 1 };

void BFS(int y, int x);
void biggest();
void init();
int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n >> m;
    char temp;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> graph[i][j];
            if (graph[i][j] == 'L') {
                land.push(make_pair(i, j));         //땅으로 인식 된 좌표는 저장합니다.
            }
        }
    }
    while (!land.empty()) {             //앞서 저장한 땅 좌표를 모두 탐색합니다.
        int y = land.front().first;
        int x = land.front().second;
        land.pop();
        BFS(y, x);                      
        biggest();                  //구한 최단 거리 중 가장 큰 값을 저장합니다.
        init();                     
    }
    cout << result;

    return 0;
}
void BFS(int y, int x) {
    queue<pair<int, int>> curL;
    curL.push(make_pair(y, x));
    int cury, curx;
    while (!curL.empty()) {
        y = curL.front().first;
        x = curL.front().second;
        curL.pop();
        for (int i = 0; i < 4; i++) {       //한 좌표의 상,하,좌,우 를 탐색합니다.
            cury = y + goy[i];
            curx = x + gox[i];
            if (!visited[cury][curx] && -1 < cury && cury < n && -1 < curx && curx < m && graph[cury][curx] == 'L') {           //방문하지 않았고, 좌표가 땅(L)이며, 그래프 범위를 넘어가지 않는 경우
                visited[cury][curx] = true;                 //방문했다고 표기합니다.
                road[cury][curx] = road[y][x] + 1;          //시작 점에서 한칸 이동한 값을 저장합니다.
                curL.push(make_pair(cury, curx));
            }
        }
    }
}
void biggest() {
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (road[i][j] != 0) {
                result = max(result, road[i][j]);
            }
        }
    }
}
void init() {
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            road[i][j] = 0;
            visited[i][j] = false;
        }
    }
}

후기 및 개선할 점

시작점을 visited에 체크를 안해주어 몇번 틀렸습니다가 나왔다. 좀 꼼꼼히 봐야할 필요가 있다ㅠ