[백준] 다리 만들기 2146번 (c++)

출처 : 2146번: 다리 만들기 (acmicpc.net)

2146번: 다리 만들기

풀이 방법

일단 각각의 섬들을 구분하기 위해 섬에 번호를 붙여 bfs를 통해 land배열에 넣어 주었다.

거리를 구할 때 중복된 경우를 처리하지 않기 위해 섬의 고유 넘버가 작은 쪽에서 큰 쪽으로 가는 경우만 처리했다.

(큰 쪽에서 작은 쪽으로 가는 길과 작은 쪽에서 큰 쪽으로 가는 길이 똑같기 때문)

for문을 통해 맵 전체를 돌며(완전 탐색) s_bfs함수를 통해 bfs를 해주는데 이때 만약 다음 칸이 0이면 len++ 해준 후 

큐에 push 하고 섬의 번호가 자신보다 크면 return len을 통해 거리를 리턴해 준다.

만약 섬의 고유 번호가 자신보다 작거나 같은 경우는 무시해 준다.

#include <bits/stdc++.h>
using namespace std;

int N, ans = 987654321;
int land[101][101], temp[101][101], visited[101][101];
int dx[4] = {0, 0, -1, 1};
int dy[4] = {-1, 1, 0, 0};


void bfs(int y, int x, int cnt) {
    queue<pair<int, int>> q;
    q.push(make_pair(y, x));
    visited[y][x] = 1;
    land[y][x] = cnt;
    while(!q.empty()) {
        int yy = q.front().first;
        int xx = q.front().second;
        q.pop();
        for (int i = 0;i < 4;i++) {
            int ny = yy + dy[i];
            int nx = xx + dx[i];
            if (ny >= 0 && ny < N && nx >= 0 && nx < N && visited[ny][nx] == -1 && land[ny][nx] == 1) {
                visited[ny][nx] = 1;
                q.push(make_pair(ny, nx));
                land[ny][nx] = cnt;
            }
        }
    }
}

void make_land() { // 각 섬에 고유 번호 붙이기 
    int cnt = 1;
    memset(visited, -1, sizeof(visited));
    for (int i = 0;i < N;i++) {
        for (int k = 0;k < N;k++) {
            if (visited[i][k] == -1 && land[i][k] != 0) {
                bfs(i, k, cnt);
                cnt++; // 섬 변
            }
        }
    }
}

int s_bfs(int y, int x) {

    memset(visited, -1, sizeof(visited));
    int land_num = land[y][x]; // 섬 번호

    queue<pair<int,pair<int, int>>> q;
    q.push(make_pair(y, make_pair(x, 0))); // y좌표, x 좌표, 거리 
    visited[y][x] = 1;
    while(!q.empty()) {
        int yy = q.front().first;
        int xx = q.front().second.first;
        int len = q.front().second.second;
        q.pop();
        for (int i = 0;i < 4;i++) {
            int ny = yy + dy[i];
            int nx = xx + dx[i];
            if (ny >= 0 && ny < N && nx >= 0 && nx < N && visited[ny][nx] == -1) {
                if (land[ny][nx] == 0) { // 바다인 경우
                    q.push(make_pair(ny, make_pair(nx, len+1)));
                    visited[ny][nx] = 1;
                }
                if (land[ny][nx] > land_num)    return len; // 자신 보다 넘버가 큰 다른 섬을 만난 경우
            }
        }
    }
    return 987654321; // 답이 없는 경우 큰 값 reutrn
}

void solve() {

    for (int i = 0;i < N;i++) {
        for (int k = 0;k < N;k++) {
            if (land[i][k] != 0) {
                ans = min(ans, s_bfs(i, k)); //최소 길이 구하기
            }
        }
    }
}

int main() {
    cin >> N;
    for (int i = 0;i < N;i++) {
        for (int k = 0;k < N;k++) {
            cin >> land[i][k];
        }
    }
    make_land();
    solve();
    cout << ans;
    return 0;
}