백준 2146 다리 만들기 (C++)

2146번: 다리 만들기

이 문제의 경우 두가지 순서로 알고리즘을 구현할 수 있다.

1. 각 섬들에 번호 붙이기
2. 섬들간의 최단 거리 구하기

각 섬들에게 번호를 정하는 부분이 findLand() 함수 부분이다. BFS를 이용해 붙어있는 땅들에게 번호를 붙여주는데 처음에 1로 주어졌기에 2부터 시작했다. 최단 거리 구하기는 각 섬마다 돌아가면서 BFS로 바다를 건너면서 다른 섬에 도착할 때까지의 최단 거리를 구해준다.
전역 변수와 지역 변수 이름을 똑같이 사용하여 시간을 낭비하는 실수를 했다. 집중하자.

#include <iostream>
#include <algorithm>
#include <queue>
#include <cstring>

using namespace std;

int N, res = 987654321;
int A[101][101];
int dy[4] = { -1,1,0,0 };
int dx[4] = { 0,0,-1,1 };
bool visit[101][101];

void findLand(int i,int j, int count) {
    queue<pair<int, int>> q;

    A[i][j] = count;
    q.push({ i,j });

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

        q.pop();

        for (int i = 0; i < 4; i++) {
            int ny = y + dy[i];
            int nx = x + dx[i];

            if (ny < 0 || nx < 0 || ny >= N || nx >= N) continue;
            if (A[ny][nx] == 0 || A[ny][nx] == count) continue;

            q.push({ ny,nx });

            A[ny][nx] = count;
        }
    }
}

void bfs(int num) {
    queue<pair<pair<int, int>, int>> q;

    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if (A[i][j] == num) {
                visit[i][j] = true;
                q.push({ {i,j},0 });
            }
        }
    }

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

        q.pop();

        for (int i = 0; i < 4; i++) {
            int ny = y + dy[i];
            int nx = x + dx[i];

            if (ny < 0 || nx < 0 || ny >= N || nx >= N) continue;
            if (A[ny][nx] != 0 && A[ny][nx] != num) {
                res = min(res, n);
                return;
            }
            if (visit[ny][nx]) continue;

            visit[ny][nx] = true;
            q.push({ {ny,nx},n + 1 });
        }
    }
}

void solution() {
    int count = 2;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if (A[i][j] == 1) {
                findLand(i, j, count);
                count++;
            }
        }
    }
    
    for (int i = 2; i < count; i++) {
        memset(visit, false, sizeof(visit));
        bfs(i);
    }

    cout << res;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    cin >> N;

    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cin >> A[i][j];
        }
    }

    solution();

    return 0;
}