[백준 2146] 다리 만들기

백준 2146

🔍 알고리즘 분류

• BFS

💡 문제 풀이

1. 나라 넘버링: bfs를 이용하여 육지가 붙어있는 덩어리에 모두 같은 숫자 부여
2. 다리 놓기
   1) 항상 출발 대륙의 가장자리에서 시작
   2) 대륙이 아닌 경우 계속 다리 놓으며 길이 계산
   3) 출발 대륙과 다른 대륙에 도착했을 경우 다리 길이 계산 후 정답 갱신

📄 코드

• C++

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

using namespace std;

int N;
int arr[100][100];
int section[100][100];
bool visited[100][100];
int distances[100][100];
int answer = 10000;

// 나라 넘버링
void bfs(int x, int y, int country) {
    int dx[4] = {-1, 1, 0, 0};
    int dy[4] = {0, 0, -1, 1};

    queue<pair<int, int>> q;

    visited[x][y] = true;
    section[x][y] = country;
    q.push(make_pair(x, y));

    while (!q.empty()) {
        x = q.front().first;
        y = q.front().second;
        q.pop();
        
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];

            if (nx >= 0 && nx < N && ny >= 0 && ny < N) {

                if (arr[nx][ny] == 1 && visited[nx][ny] == false) {
                    visited[nx][ny] = true;
                    section[nx][ny] = country;
                    q.push({nx, ny});
                }
            }
        }
    }
}

// 다리 놓기
void make_bridge(int x, int y) {
    int dx[4] = {-1, 1, 0, 0};
    int dy[4] = {0, 0, -1, 1};

    queue<pair<int, int>> q;
    int start_country_num = section[x][y];

    q.push(make_pair(x, y));

    bool flag = false;

    while (!q.empty()) {
        x = q.front().first;
        y = q.front().second;
        q.pop();
        
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            
            if (nx >= 0 && nx < N && ny >= 0 && ny < N) {
                // 다리 놓기
                if (arr[nx][ny] == 0 && distances[nx][ny] == 0) {
                    distances[nx][ny] = distances[x][y] + 1;
                    q.push(make_pair(nx, ny));
                } 
                // 출발 대륙과 다른 대륙에 도착했을 경우
                else if (arr[nx][ny] == 1 && section[nx][ny] != start_country_num && distances[nx][ny] == false) {
                    if (distances[x][y] < answer) {
                        answer = distances[x][y]; // 정답 갱신
                    }
                }
            }
        }
    }
}

int main() {
    cin >> N;
    
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cin >> arr[i][j];
            visited[i][j] = false;
            distances[i][j] = 0;
        }
    }

    int country = 0;

    // 나라 넘버링
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if (arr[i][j] == 1 && visited[i][j] == false) {
                country++;
                bfs(i, j, country);
            }
        }
    }

    // 나라의 가장 자리일때만 자리 놓기 시작
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if (arr[i][j] == 1) {
                make_bridge(i, j);
            }
            // 거리 정보 초기화
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    distances[i][j] = 0;
                }
            }
        }
    }

    cout << answer;

    return 0;
}