[BOJ] 17472번 | 다리 만들기 2 (C++)

🔗문제 보러가기

17472번: 다리 만들기 2

 

👨‍💻풀이 과정

 

BFS + DFS + 최소 신장 트리(MST) 알고리즘을 구현해야 풀 수 있는, 대단히 체력적으로 힘든 문제였습니다. 그래도 문제에서 주어진 조건들이 까다롭진 않아, 구현만 제대로 한다면 통과는 쉽게 되네요. 제가 푼 과정은 다음과 같습니다.

 

1. 주어진 입력을 2차원 배열에 저장하되, 땅(1)은 1이 아니라 엄청 큰 다른 숫자(1억)로 대신 채워줍니다.
2. BFS 알고리즘을 통해, 각 섬의 번호를 해당 섬의 영역에 채워줍니다.
3. DFS 알고리즘을 통해, 서로 다른 번호의 섬 끼리의 거리를 별도의 배열(distances)에 저장해줍니다.
   • distances[i][j] 는 i번 섬에서 j번 섬으로 가는 거리이며, 초기값은 매우 큰 숫자(1억)으로 저장
   • 거리가 1 이하이거나, 다리를 꺾어서 지어야 연결 가능한 경우에는 건너뛰기
   • 이미 값이 저장되어 있는 경우에는 새 값과 비교하여 더 작은 값으로 갱신
4. 최소 신장 트리 알고리즘을 적용해, 각 섬을 잇는 최솟값을 구해서 출력합니다.
   • 저는 프림의 알고리즘(Prim's Algorithm)을 사용했습니다.

 

위처럼 과정은 크게 4가지인데, 각 과정을 함수로 구현하고 중간 테스트를 진행해 문제가 없는지 점검하였습니다. 구현 문제는 이렇게 진행해야, 시간을 효율적으로 사용할 수 있더라구요.

 

✏️소스 코드 및 결과

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

using namespace std;
#define FAST_IO ios::sync_with_stdio(false); cout.tie(NULL); cin.tie(NULL);

using Position = pair<int, int>;    // <행, 열>
using Data = pair<int, int>;        // <거리, 섬 번호>

vector<vector<int>> Directions { {-1, 0}, {1, 0}, {0, -1}, {0, 1} };  // 상하좌우

const int SEA = 0;
const int MAX = 100000000;
int N, M;


void Input(vector<vector<int>>& field);
void SetIsland(vector<vector<int>>& field, int& islandNumber);
void BFS(vector<vector<int>>& field, const int islandNumber, int row, int col);
void GetIslandDistances(const vector<vector<int>>& field, vector<vector<int>>& distances);
void DFS(const vector<vector<int>>& field, vector<vector<int>>& distances, const vector<int>& direction, int islandNumber, int row, int col, int distance);
int Prim(const vector<vector<int>>& distances, int start);

int main() {
    FAST_IO
    cin >> N >> M;

    int islandNumber = 1;
    vector<vector<int>> field(N, vector<int>(M));
    
    Input(field);
    SetIsland(field, islandNumber);

    vector<vector<int>> distances(islandNumber, vector<int>(islandNumber, MAX));
    GetIslandDistances(field, distances);

    int answer = Prim(distances, 1);
    cout << answer;
    return 0;
}

int Prim(const vector<vector<int>>& distances, int start) {
    vector<bool> MST(distances.size(), false);
    MST[start] = true;

    priority_queue<Data, vector<Data>, greater<Data>> edges;
    for (int i = 1; i < distances[start].size(); i++) {
        if (i == start or distances[start][i] == MAX)
            continue;
        edges.emplace(distances[start][i], i);
    }

    int answer = 0;
    while (!edges.empty()) {
        int distance = edges.top().first;
        int islandNumber = edges.top().second;
        edges.pop();

        if (MST[islandNumber])
            continue;
        
        MST[islandNumber] = true;
        answer += distance;

        for (int i = 1; i < distances[islandNumber].size(); i++) {
            if (i == islandNumber or MST[i] or distances[islandNumber][i] == MAX)
                continue;
            edges.emplace(distances[islandNumber][i], i);
        }
    }

    for (int i = 1; i < MST.size(); i++)
        if (!MST[i])
            return -1;
    return answer;
}


void DFS(const vector<vector<int>>& field, vector<vector<int>>& distances, const vector<int>& direction, int islandNumber, int row, int col, int distance) {
    int nextRow = row + direction[0];
    int nextCol = col + direction[1];

    if (nextRow < 0 or nextRow >= N or nextCol < 0 or nextCol >= M)
        return;
    if (field[nextRow][nextCol] == islandNumber)
        return;
    if (field[nextRow][nextCol] == SEA) {
        DFS(field, distances, direction, islandNumber, nextRow, nextCol, distance + 1);
        return;
    }

    if (distance <= 1)
        return;

    int otherIslandNumber = field[nextRow][nextCol];
    int newDistance = min(distance, distances[islandNumber][otherIslandNumber]);

    distances[islandNumber][otherIslandNumber] = newDistance;
    distances[otherIslandNumber][islandNumber] = newDistance;
}

void GetIslandDistances(const vector<vector<int>>& field, vector<vector<int>>& distances) {
    for (int row = 0; row < N; row++) {
        for (int col = 0; col < M; col++) {
            if (field[row][col] == SEA)
                continue;
            
            for (const auto& direction : Directions)
                DFS(field, distances, direction, field[row][col], row, col, 0);
        }
    }
}

void Input(vector<vector<int>>& field) {
    for (int row = 0; row < N; row++)
        for (int col = 0; col < M; col++) {
            int value;
            cin >> value;

            value = (value == 1) ? MAX : value;
            field[row][col] = value;
        }
}

void SetIsland(vector<vector<int>>& field, int& islandNumber) {
    for (int row = 0; row < N; row++) {
        for (int col = 0; col < M; col++) {
            if (field[row][col] == SEA or field[row][col] < islandNumber)
                continue;
            BFS(field, islandNumber++, row, col);
        }
    }
}

void BFS(vector<vector<int>>& field, const int islandNumber, int row, int col) {
    queue<Position> positions;
    positions.emplace(row, col);
    field[row][col] = islandNumber;

    while (!positions.empty()) {
        int currentRow = positions.front().first;
        int currentCol = positions.front().second;
        positions.pop();

        for (const auto& direction : Directions) {
            int nextRow = currentRow + direction[0];
            int nextCol = currentCol + direction[1];

            if (nextRow < 0 or nextRow >= N or nextCol < 0 or nextCol >= M)
                continue;
            if (field[nextRow][nextCol] == SEA or field[nextRow][nextCol] == islandNumber)
                continue;
            
            field[nextRow][nextCol] = islandNumber;
            positions.emplace(nextRow, nextCol);
        }
    }
}