2146번

2146번 - 다리 만들기

다리의 최솟값, 즉 최단거리를 구하는 것이고, 좌표내에서 이동은 비용이 1칸으로 동일하므로 BFS로 풀어야겠다는 생각을 하였다.

풀려고 하는데 입력값이 모두 1로 주어졌기 때문에 대륙간의 연결에 어려움이 있다고 생각했고,

대륙을 각각 다른 값으로 묶어줘야했기 때문에 처음에 BFS를 대륙을 다른 번호로 묶어주는 방식으로 사용했다.

(대륙을 묶는 방식은 DFS를 사용해도 될 것 같다)

대륙을 묶은 값 = map2 

대륙을 묶은 후에는 맵 전체에 대해서 BFS를 하였다.

단, BFS는 어떠한 대륙에서만 시작할 수 있다는 조건을 달았다.

그리고 BFS에서 바다로 다리를 놓다가 시작한 대륙의 번호와 다른 대륙을 만나면 그 값을 체크해서 가장 작은 값으로 업데이트 해줬다.

각각의 점들에 대해서 거리를 구하기 위해 dist 와 check2 를 매 점마다 새로 선언해서 풀었다.

<정답 코드>

#include<iostream>
#include<queue>
#include<algorithm>
#include<string.h>
using namespace std;
int N;
int map[101][101];
int map2[101][101];
bool check[101][101];
int dx[4] = { 0,0,1,-1 };
int dy[4] = { 1,-1,0,0 };
int ans = 987654321;
 
int main()
{
    cin >> N;
 
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            cin >> map[i][j];
        }
    }
    /////////////////////////////////////////////////////대륙 나누기
 
    int numOfcontinent = 0;
 
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            if (map[i][j] == 1 && !check[i][j])
            {
                numOfcontinent++;
                queue<pair<int, int>> q;
                q.push(make_pair(i, j));
                map2[i][j] = numOfcontinent;
                check[i][j] = true;
 
                while (!q.empty())
                {
                    int x = q.front().first;
                    int y = q.front().second;
                    q.pop();
 
                    for (int d = 0; d < 4; d++)
                    {
                        int nx = x + dx[d];
                        int ny = y + dy[d];
                        if (nx >= 0 && ny >= 0 && nx < N && ny < N && !check[nx][ny] && map[nx][ny] == 1)
                        {
                            q.push(make_pair(nx, ny));
                            check[nx][ny] = true;
                            map2[nx][ny] = numOfcontinent;
                        }
                    }
                }
 
            }
        }
    }
 
    ///////////////////////////////////////////////////////////////////////////////////
 
    ///////////////////////////////다리놓기
 
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            if (map[i][j] != 0)
            {
                int dist[101][101];
                bool check2[101][101];
                int num;
 
                memset(dist, 0, sizeof(dist));
                memset(check2, false, sizeof(check2));
 
                queue<pair<int, int>> q;
                q.push(make_pair(i, j));
                dist[i][j] = 0;
                check2[i][j] = true;
                num = map2[i][j];
 
                while (!q.empty())
                {
                    int x = q.front().first;
                    int y = q.front().second;
                    q.pop();
 
                    for (int d = 0; d < 4; d++)
                    {
                        int nx = x + dx[d];
                        int ny = y + dy[d];
                        if (nx >= 0 && ny >= 0 && nx < N && ny < N && !check2[nx][ny] && map2[nx][ny] == 0)
                        {
                            q.push(make_pair(nx, ny));
                            check2[nx][ny] = true;
                            dist[nx][ny] = dist[x][y] + 1;
                        }
                        else if (nx >= 0 && ny >= 0 && nx < N && ny < N && map2[nx][ny] != num && map2[nx][ny] != 0)
                        {
                            ans = min(ans, dist[x][y]);
                        }
                    }
                }
 
            }
        }
    }
    
    cout << ans << endl;
    
    return 0;
}