[c++] 백준 #2146 다리만들기

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

<풀이방법>

백준문제 #7576 토마토 문제를 풀었다면 비슷하게 풀 수 있다.

각 섬에서부터 바다로 뻗어나가면서 섬에서의 거리를 측정하다가, 다른 섬에서 이미 거리를 측정한 부분을 만나는 경우, 두 거리를 더해서 그 합의 최소값을 구하면 된다. 이때 각 섬이 어디있는 지, 사전에 labeling을 해둬야하기 때문에 DFS를 돌리고, 그 다음에 거리를 BFS를 이용해서 구하면 된다. DFS를 이용하여 각 섬에 대해 labeling하는 것은 백준문제 #2667 단지번호 붙이기를 풀었다면 그냥 그때 쓴 코드 재활용하면 된다. 

    #include <iostream>
    #include <string>
    #include <vector>
    #include <stdio.h>
    #include <stdlib.h>
    #include <time.h> 
    #include <string.h>
    #include <cstdio>
    #include <math.h>
    #include <map>
    #include <algorithm>
    #include <queue>
    #include <utility>
    using namespace std;
 
    // variables
    int map_[100][100] = {0,}; // stores the map info(1=island / 0=sea)
    int visit[100][100] = {0,}; // stores which (x,y) is visited or not
    int dist[100][100] = {0,}; // stores the distance info 
    int dx[4] = {-1, 0, 1, 0}; // moving direction x
    int dy[4] = {0, 1, 0, -1}; // moving direction y
    int N; // length of map
    int M; // width of map
    queue<pair<int, int>> SP; // array of starting points
 
    int islands = 1; // num for labeling islands
    int min_d = 200*200; // num for calculating minimum distance
 
    void DFS(int x, int y, int islands)
    {
        visit[x][y] = islands;
        int new_x, new_y;   
        // if valid x, y coordinate
        for (int i=0; i< 4; i++)
        {
            new_x = x + dx[i];
            new_y = y + dy[i];
            if (new_x < 0 || new_y < 0 || new_x >= N || new_y >= N) continue;
            // if movable from current location &  didn't searched before, do DFS        
            if (visit[new_x][new_y] == 0 && map_[new_x][new_y] == 1) DFS(new_x,new_y,islands); 
        }
    }
 
    void BFS()
    {
        queue<pair<int, int>> Q; 
        while(!SP.empty())
        {
            pair<int, int> A = SP.front(); // dequeue all starting nodes!
            SP.pop();
            Q.push(A);
        }
        // First in first out by using queue
        while (!Q.empty()) 
        {
            pair<int, int> A = Q.front(); // dequeue the first node!
            Q.pop();
            
            int new_x, new_y; 
            // if valid x, y coordinate
            for (int i=0; i< 4; i++)
            {
                new_x = A.first + dx[i];
                new_y = A.second + dy[i];
                
                if (new_x < 0 || new_y < 0 || new_x >= N || new_y >= N ) continue;
 
                // if movable from current location &  didn't searched before, enqueue new coordinate
                if (visit[new_x][new_y] == 0 && map_[new_x][new_y] == 0) 
                {
                    pair<int, int> N = make_pair(new_x, new_y);
                    Q.push(N); 
                    visit[new_x][new_y] = visit[A.first][A.second];
                    map_[new_x][new_y] = 1;
                    if (dist[new_x][new_y] == 0) dist[new_x][new_y] = dist[A.first][A.second] + 1;
                }
 
                // if new coordinate is already searched by other island
                else if (visit[new_x][new_y] != 0 && visit[new_x][new_y] != visit[A.first][A.second])
                {
                    min_d = min(min_d,dist[new_x][new_y] + dist[A.first][A.second]);
                }
            }    
        }
    }
 
 
    int main()
    {
        ios_base :: sync_with_stdio(false);
        cin.tie(NULL);
        cout.tie(NULL);            
        cin >> N;
        int temp;
        for (int i=0;i<N;i++)
        {
            for (int j=0; j<N;j++)
            {
                cin >> temp;
                map_[i][j] = temp;
                if(temp == 1) 
                {
                    pair<int, int> sp = make_pair(i,j); 
                    SP.push(sp);
                }
            }
        }
 
            for (int i=0;i<N;i++)
            {
                for(int j=0; j<N;j++)
                {
                    if (visit[i][j] == 0 && map_[i][j] == 1) 
                    {
                        islands = islands + 1;
                        DFS(i,j,islands);
                    }
                }
            }
        BFS();
        cout << min_d << '\n';
 
        return 0;
    }