[백준/Baekjoon] 2146 다리 만들기 C++ :: BFS

https://www.acmicpc.net/problem/2146

2146번: 다리 만들기

---

1. Logic

특정 지점에서 출발하는 것을 선택하지 못하고 선택하더라도 그 지점에서 최솟값이 나오리라고 장담할 수 없다.

그렇기 때문에 도착한 섬이 출발한 섬과 다른 섬인지를 구별하는 아이디어를 떠올려야 하는 문제이다.

문제에서는 섬을 1로 입력받지만 나는 처음에 -1로 받은 뒤 각 섬마다 섬 내부에서 BFS를 돌아서 각 섬에 숫자를 매겨줬다. 각 섬의 번호가 매겨지면 섬마다 BFS를 돌며 다른 섬까지의 최솟값을 구한다.

 

순서대로 깔끔하게 적어보자면

1. 섬마다 번호를 매겨 서로 다른 섬을 구분해준다.

2. 각 섬에서 출발하는 BFS를 돌며 다른 섬까지의 최소 거리를 구한다.

---

2. Code

#include <bits/stdc++.h>

using namespace std;

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

vector<vector<int>> input(101, vector<int>(101, 0));
vector<vector<bool>> vis(101, vector<bool>(101, false));

void classificationLand(int yy, int xx, int num) {
    queue<pair<int, int>> q;

    q.push({yy, xx});
    input[yy][xx] = num;

    while (!q.empty()) {
        int x = q.front().second;
        int y = q.front().first;

        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) continue;
            if (input[ny][nx] != -1) continue;

            input[ny][nx] = num;
            q.push({ny, nx});
        }
    }
}

int bfs(int num) {
    queue<pair<int, int>> q;
    int dis = 0;

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (input[i][j] == num) {
                q.push({i, j});
                vis[i][j] = true;
            }
        }
    }

    while (!q.empty()) {
        int cur = q.size();
        for (int i = 0; i < cur; i++) {
            int x = q.front().second;
            int y = q.front().first;

            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) continue;
                if (input[ny][nx] == num) continue;
                if (vis[ny][nx]) continue;

                vis[ny][nx] = true;
                if (input[ny][nx] != 0 && input[ny][nx] != num) {
                    return dis;
                }
                q.push({ny, nx});
            }
        }
        dis++;
    }

    return dis;
}

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

    cin >> n;

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> input[i][j];
            if (input[i][j] == 1) {
                input[i][j] = -1;
            }
        }
    }

    int num = 1;

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (input[i][j] == -1) {
                classificationLand(i, j, num);
                num++;
            }
        }
    }

    int answer = 0x3f3f3f3f;

    for (int i = 1; i < num; i++) {
        answer = min(answer, bfs(i));
        vis.assign(101, vector<bool> (101, false));
    }

    cout << answer;
}

---

3. Feedback

섬에 번호를 매기는 아이디어가 필요하지만 한단계만 생각해 보면 되는 문제라 그렇게 어렵지는 않았다.

알고리즘 Solve 후 제가 생각한 Logic을 기록하는 개인 공부 블로그입니다.
내용 중 최적화가 가능한 부분등은 언제든지 댓글로 틀린 부분 및 피드백 주시면 공부 및 반영하겠습니다🧐