[백준/C++] #2146 다리 만들기 (Flood Fill / BFS)

문제

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

 

 

알고리즘

: BFS 이용한 Flood Fill

 

알고리즘은 쉬웠는데, 조건 때문에 조금 헤매어서 시간이 걸렸다.ㅠ

bfs를 섬에 번호 매길때 한번,  섬들 간 최단 거리 구할 때 한번 사용했다. 다음에는 dfs로도 풀어봐야겠다.

 

그리고 fill, memset 초기화 함수에 대해서도 잘 알아두자!!

 

코드 + 풀이

1. 섬 찾아 섬을 이루는 땅들에 동일한 번호 붙이기 -> findLand()
2. 섬들간의 최단 거리 구하기 -> bfs()

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#define MAX 101
#define INF 987654321
// 2146
/*
섬과 섬을 잇는 짧은 다리 
지도가 주어질 때, "가장 짧은 다리 하나"를 놓아 두 대륙을 연결하자
flood fill

memset(arr, 0, sizeof(arr)) -> -1, 0로만 초기화 가능. 속도는 월등히 빠름. 
fill(arr, arr+N, 0) -> 원하는 값으로 초기화 가능. 느리지만 안전함. 
-> fill(arr, arr+5, -1);
-> fill(&arr2[0][0], &arr2[0][0] + 5*5, 0);
*/

using namespace std;

// 전역 변수, 함수
int n, res = 987654321;
vector<vector<int>> map(MAX, vector<int>(MAX)); // 지도 (y, x)
vector<vector<bool>> visit(MAX, vector<bool>(MAX)); // 방문 여부 나타냄 (y, x)
vector<pair<int, int>> dxy = { {1, 0}, {0, -1}, {-1, 0}, {0, 1} }; // (y, x)

// 함수
// bfs 통해 섬을 구성하는 땅들을 모로지 찾아 땅에 번호 붙이기
void findLand(int i, int j, int count) {
    queue<pair<int, int>> qq; // findLand

    map[i][j] = count; // 번호 부여
    qq.push({i, j}); // 큐에 넣기 // i == y, j == x 

    while (!qq.empty()) {
        auto now = qq.front();
        int y = now.first;
        int x = now.second;

        qq.pop();

        for (int i = 0; i < 4; i++) {
            int ny = y + dxy[i].first;
            int nx = x + dxy[i].second;
            
            if (ny < 0 || ny >= n || nx < 0 || nx >= n) continue;
            if (map[ny][nx] != 1) continue; // 현재 번호가 1인 섬만 탐색하기 위해 -> visit배열 따로 필요 없음

            qq.push({ny, nx });
            map[ny][nx] = count; // 여기서 표시 해두기에
        }

    }
}

// 섬들간의 최단 거리 구하기
void bfs(int num) { // 섬 번호. 섬 개수만큼 반복됨
    queue<pair<pair<int, int>, int>> q; // bfs ((y, x), n)

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (map[i][j] == num) { // 해당 섬이면 
                visit[i][j] = true; // 방문 확인
                q.push({{i,j}, 0}); // 거리 0으로 큐에 넣기
            }
        }
    }

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

        q.pop();

        for (int i = 0; i < 4; i++) {
            int ny = y + dxy[i].first;
            int nx = x + dxy[i].second;

            if (ny < 0 || ny >= n || nx < 0 || nx >= n) continue; // 경계를 넘어선다면

            if (map[ny][nx] != 0 && map[ny][nx] != num) { // 바다가 아니고, 기존의 섬이 아니면, 
                res = min(res, nn); // 거리 갱신
                return; // 첫 값이 최소일테니까 리턴
            }

            if (visit[ny][nx]) continue; // 이미 방문했었다면

            visit[ny][nx] = true; // 방문 처리

            q.push({ {ny,nx}, nn + 1 }); // 거리 증가시킴
        }
    }
}

// 로직
void solution() {
    // 섬들에 번호 붙이기
    int count = 2;
    for (int i = 0; i < n; i++) 
        for (int j = 0; j < n; j++) {
            if (map[i][j] == 1) { // 섬이면
                findLand(i, j, count);
                count++;
            }
        }

    // 섬들간의 최단 거리 구하기
    for (int i = 2; i < count; i++) { // 섬의 개수만큼
        for (auto& row : visit) {
            fill(row.begin(), row.end(), false); // 2차원 배열 초기화
        }
        bfs(i);
    }

    // 출력
    cout << res;
}

// main
int main() {
    ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    // 입력
    cin >> n;

    map.resize(n, vector<int>(n));
    visit.resize(n, vector<bool>(n));

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> map[i][j]; // 1이면 육지, 0이면 바다
        }
    }

    // 로직
    solution();

    return 0;
}