[BOJ/2146번다리만들기] c++ / BFS

문제

섬과 섬을 잇는 다리 중 가장 짧은 다리의 길이를 구하는 문제

-두개 이상의 섬이 주어짐

-땅은 1, 바다는 0으로 표시됨

 

생각

섬마다 번호 표시해서 그룹화 시켜야겠다 생각
섬에서 다른 섬까지의 거리 표시
섬 개수만큼 각각 BFS 해서 짧은 거리 저장

-30에서 틀렸습니다 -> 최솟값 초기화를 100으로 해놨었음

-80에서 틀렸습니다 -> 4번 과정 안에 5~ 다 넣어서 했었음 => 번호가 이상하게 매겨짐 => 처음에 몽땅 섬을 넣어줘야 함 !

 

문제풀이

1.땅을 찾아 섬번호를 매겨줘야함 ( Group )

1-1.map에서 섬번호가 없는 땅이 나오면 BFS 탐색

1-2.상하좌우에 인접한 섬번호가 없는 땅이 나오면, 섬번호 저장 + 큐에 푸쉬

2.map칸을 vis칸의 값으로 변경해줌

3.각 섬마다 가장 짧은 다리 길이 구해야 함

3-1.vis를 -1로 초기화해줌

4.map에서 섬을 찾아 모두 큐에 푸쉬해줌 ( 이 과정을 안 걸치면 탐색이 꼬임 )

5.BFS 탐색

5-1.섬번호와 일치하는 땅이 나오면, 방문표시 + 큐에 푸쉬

5-2.바다가 나오면, 방문표시( 기준칸 + 1 ) + 큐에 푸쉬

5-3.섬번호와 일치하지 않는 다른 섬이 나오면, 최솟값 비교하고 방문표시

6.섬별로 BFS 탐색이 끝날 때 마다, Re와 result값 비교해서 최솟값 구함

7.Re 출력

 

 

코드

#include <iostream>
#include <algorithm>
#include <queue>
#include <cstring>
using namespace std;
#define X first
#define Y second
int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0, 0};
int N, num = 0, cnt = 0;
int map[101][101];
int vis[101][101];
int result = 10001, Re = 10001;
void resetvis()
{
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
            vis[i][j] = -1;
    }
}
void Group()
{
    queue<pair<int, int>> Q;

    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            if (!map[i][j] || vis[i][j])
                continue;
            num++;

            vis[i][j] = num;
            Q.push({i, j});

            while (!Q.empty())
            {
                pair<int, int> cur = Q.front();
                Q.pop();

                for (int dir = 0; dir < 4; dir++)
                {
                    int nx = cur.X + dx[dir];
                    int ny = cur.Y + dy[dir];

                    if (nx < 0 || nx >= N || ny < 0 || ny >= N)
                        continue;
                    if (!map[nx][ny] || vis[nx][ny])
                        continue;

                    vis[nx][ny] = num;
                    Q.push({nx, ny});
                }
            }
        }
    }
}
void BFS()
{
    queue<pair<int, int>> Q;

    for (int n = 1; n <= num; n++)
    {
        resetvis();
        result = 10001;

        for (int i = 0; i < N; i++)
            for (int j = 0; j < N; j++)
            {
                if (map[i][j] != n || vis[i][j] != -1)
                    continue;
                vis[i][j] = 0;
                Q.push({i, j});
            }

        while (!Q.empty()) {
            pair<int, int> cur = Q.front();
            Q.pop();

            for (int dir = 0; dir < 4; dir++) {
                int nx = cur.X + dx[dir];
                int ny = cur.Y + dy[dir];

                if (nx < 0 || nx >= N || ny < 0 || ny >= N)
                    continue;

                if (map[nx][ny] == n && vis[nx][ny] == -1) {
                    vis[nx][ny] = 0;
                    Q.push({nx, ny});
                }

                if (map[nx][ny] == 0 && vis[nx][ny] == -1) {
                    vis[nx][ny] = vis[cur.X][cur.Y] + 1;
                    Q.push({nx, ny});
                }
                
                if (map[nx][ny] != n && map[nx][ny] != 0 && vis[nx][ny] == -1) {
                    if (result > vis[cur.X][cur.Y])
                        result = vis[cur.X][cur.Y];

                    vis[nx][ny] = 1;
                }
            }
        }

        if (Re > result)
            Re = result;
    }
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> N;
    for (int i = 0; i < N; i++)
        for (int j = 0; j < N; j++)
            cin >> map[i][j];

    Group();
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            map[i][j] = vis[i][j];
        }
    }
    BFS();
    cout << Re;
}