[백준(BOJ)] 2589번 보물섬 C++

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

2589번: 보물섬

 

 

어떤 문제인가?

입력을 받으면 땅인 부분과 바다인 부분이 생긴다.

 

한 땅 덩어리가 하나의 연결 요소라고 생각하면 된다.

이때 연결 요소 내에서 한 정점에서 다른 정점으로 가는 최대 거리를 출력하면 되는 것이다.

 

 

 

접근 방법

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

한 정점에서 상, 하, 좌, 우로 움직이기 위한 배열이다.

 

char map[51][51];
bool visited[51][51];
int dist[51][51];

지도를 저장할 이차원 배열, 방문 여부를 저장할 이차원 배열, 이동거리를 저장할 이차원 배열을 선언한다.

 

int n, m;
cin >> n >> m;

지도의 세로  크기 n, 가로 크기 m을 선언하고 입력받는다.

 

 

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

지도를 입력받는다.

 

int bfs(int y, int x) {
    queue<pair<int, int>> q;
    q.push({x, y});

    visited[y][x] = true;
    int maxNum = 0;

    while (!q.empty()) {
        int x1 = q.front().first;
        int y1 = q.front().second;
        q.pop();

        for (int i = 0; i < 4; i++) {
            int x2 = x1 + dx[i];
            int y2 = y1 + dy[i];

            if (x2 < 0 || y2 < 0 || x2 >= m || y2 >= n) {
                continue;
            }

            if(map[y2][x2]=='W'){
                continue;
            }

            if (!visited[y2][x2]) {
                visited[y2][x2] = true;
                q.push({x2, y2});
                dist[y2][x2] = dist[y1][x1] + 1;
                maxNum = max(maxNum, dist[y2][x2]);
            }
        }
    }
    return maxNum ;
}

bfs함수를 살펴보자.

이 문제도 다른 그래프 탐색 문제와 크게 다른 부분은 없다.

 

큐와 pair를 사용해 x좌표와 y좌표를 저장하고 큐가 빌 때까지 반목해나가며 탐색한다.

 

이동한 좌표가 지도의 밖이거나 이동한 좌표의 값이 W(바다)라면 예외처리를 해준다.

 

거리를 구해야하는데 이 문제는 어디서 어디까지 이동해야하는 거리가 아니다.

문제의 입력마다  다를 것이다.

 

그래서 따로 연결요소에서 정점과 정점간의 이동거리의 최댓값을 따로 저장해야한다.

dist [ y ] [ x ] = 3은 ( x, y) 까지의 거리가 3이라는 소리이다.

 

한 칸당 이동거리가 1이므로 기존 좌표의 값 + 1을 해주면 된다.

그리고 maxNum과 비교하여 더 큰 값을 maxNum에 할당해준다.

 

큐가 비어 while문이 종료됐다면 계산된 maxNum을 리턴해준다.

 

 

 

for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
        if (map[i][j] == 'L') {
            maxNum = max(maxNum, bfs(i, j));
            reset();
        }
    }
}

이제 다시 main함수이다.

입력받은 그래프를 돌다가 땅이나오면 그 좌표로 bfs를 시작한다.

그리고 maxNum과 더 큰 값을 maxNum에 할당해준다.

 

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

다음 bfs를 하기 전, 사용한 visited, dist 배열을 초기화해준다.

 

 

cout << maxNum;

모든 땅에서 bfs를 수행하고나서 maxNum을 출력하면 끝!

 

 

 

 

무엇이 어려웠는가?

이 문제는 어디서 어디로 이동하는 것이 정해져 있지 않았다.

한 연결요소 내에서 한 정점과 다른 한 정점의 최대 최단거리를 어떻게 구해야할지 몰랐었다.

생각해보니 별거 없이 그래프를 탐색해나가며 현재 좌표까지 이동한 거리와 기존의 최대 거리를 비교하면서

갱신해나가기만 하면 됐다.

 

배운 점

이번 주에는 그래프 탐색 문제를 집중적으로 풀었다.

문제를 풀 수록 점점 실력이 느는게 느껴져서 기분이 좋다.

개강이 얼마 안 남았는데 남은 기간동안 더 열심히 하자!