[백준][2146번] 다리 만들기[cpp, c++]

백준 2146번 다리 만들기

• BFS로만 풀 수 있지만, DFS와 BFS 둘 다 이용할 수 있는 문제이다.
• https://www.acmicpc.net/problem/2146
• 풀이방법
  1) 각 나라를 구분짓기 위해 bfs나 dfs를 사용한다. 나는 bfs를 사용했다.
  2) 각 나라를 구분지은 후, 나라와 나라 사이의 최단거리를 BFS로 구한다.

2146번: 다리 만들기

#include<iostream>
#include<queue>
#include<vector>
#include<cstring>
using namespace std;
int N; //지도의 크기
int map[100][100];
bool check[100][100];
int check2[100][100];
int ans=1000000;
int nx[4] = { 1,0,-1,0 };
int ny[4] = { 0,1,0,-1 };

void bfs(int x, int y, int color) { // 나라를 구분 짓는 bfs
    queue<pair<int, int>> q;
    q.push(make_pair(x, y));
    check[x][y] = true;
    map[x][y] = color;
    while (!q.empty()) {
        int x = q.front().first;
        int y = q.front().second;
        q.pop();
        for (int i = 0; i < 4; i++) {
            int dx = nx[i] + x;
            int dy = ny[i] + y;
            if (dx >= N || dx < 0 || dy >= N || dy < 0) continue;
            if (check[dx][dy] == true || map[dx][dy] == 0) continue;
            check[dx][dy] = true;
            map[dx][dy] = color;
            q.push(make_pair(dx, dy));
        }
    }
}

void bfs2(int x, int y) { // 최단거리를 구하는 bfs
    queue<pair<int, int>> q;
    q.push(make_pair(x, y));
    check2[x][y] = 1;
    int temp = map[x][y];
    while (!q.empty()) {
        int x = q.front().first;
        int y = q.front().second;

        q.pop();
        for (int i = 0; i < 4; i++) {
            int dx = nx[i] + x;
            int dy = ny[i] + y;
            if (dx >= N || dx < 0 || dy >= N || dy < 0) continue;
            if (map[dx][dy] != 0 && temp != map[dx][dy]) { //다른 대륙 발견;
                if (ans > check2[x][y]) {
                    ans = check2[x][y];
                    //cout << ans << "\n";
                }
            }
            if (check2[dx][dy] != 0 || map[dx][dy] != 0) continue;
            check2[dx][dy] = check2[x][y] + 1;
            q.push(make_pair(dx, dy));
        }
    }
    memset(check2, 0, sizeof(check2));
}

void input() {
    cin >> N;
    int country = 2;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cin >> map[i][j];
            }
        }
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if (check[i][j] == false && map[i][j] == 1) {
                bfs(i, j, country++); // x좌표, y좌표, 나라의 구분
            }
        }
    }

    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if (map[i][j]>0) {
                bfs2(i,j); 
            }
        }
    }
    cout<< ans-1 << "\n";
}



void sol() {
    input();
}

int main(void) {
    sol();

    return 0;
}