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

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

 

 

https://lee-soo.tistory.com/39

[DFS,BFS] 백준 1707번 이분 그래프(C++)

문제만 봐도~ 

이분 그래프 느낌이..?!

 

근데 저기 나오는 정치인 참 너무하네

1개만 세워준다니

 

쨋든

 

1. 각 섬이 존재

2. 각 섬을 잇는 다리 중 최소한의 다리의 길이 구하기

 

이다

 

내가 먼저 생각한건

 

1. 각 섬의 라벨링 ( 1이면 1 2이면 2.. )

 

2. 라벨링한 섬들간의 거리를 구하기 ( 각 섬마다 )

 

 

라벨링 하는건 앞선 이분 그래프 할 때 처럼 하면 되겠지?

int main()

{

    cin >> n;

    for (int i = 0; i < n; i++)

        for (int j = 0; j < n; j++)

        {

            cin >> arr[i][j];

            if (arr[i][j])

            {

                q.push(make_pair(i, j));

                dp[i][j] = 1;

            }

        }

    for (int i = 0; i < n; i++)

    {

        for (int j = 0; j < n; j++)

        {

            if (!visited[i][j] && arr[i][j])

            {

                bfs(i, j);

                label_count++;

            }

        }

    }

void bfs(int a, int b)

{

    queue<pair<int, int>> temp;

    temp.push(make_pair(a, b));

    visited[a][b] = true;

    while (!temp.empty())

    {

        int x = temp.front().first;

        int y = temp.front().second;

        temp.pop();

        label[x][y] = label_count;

        for (int i = 0; i < 4; i++)

        {

            int nx = x + dx[i];

            int ny = y + dy[i];

            if (arr[nx][ny] == 1 && label[nx][ny] == 0 && !visited[nx][ny] && nx < n && nx >= 0 && ny < n && ny >= 0)

            {

                visited[nx][ny] = true;

                label[nx][ny] = label_count;

                temp.push(make_pair(nx, ny));

            }

        }

    }

}

 

 

 

 

이 식을 보면, 대충 감은 올 것이다.

 

앞선 dp 식은 무시하고(나중에 길이구할 때 쓸꺼임)

 

모든 i,j에 대해서 라벨링을 해준다! ( 모든 이어져 있는 섬~ )

 

그래서 뭐 bfs를 통해서 가장 가까운 애들 전부 1로 라벨링

그 다음섬은 2..

그 다음섬은 3...

 

그래서 이걸 지나면?

이 입력에대해서

 

 

 

이렇게 섬마다 라벨링이 붙게 된다

 

for (int i = 0; i < n; i++)

    {

        for (int j = 0; j < n; j++)

        {

            cout << label[i][j] << " ";

        }

        cout << "\n";

    }

이 식 사용하면 나옴

 

그 다음은 어떻게 할까?

 

앞선 dp에서 모든 섬의 위치에 대해서는 dp를 1로 고정 시켜주고

 

각 섬에서 다음 위치로 나아갈 때 마다 dp에 1을 더하는 식으로 진행하는데

 

 

 

 

label이 안 붙은 위치로 갈때는 +1을해주고

 

 

label이 붙어있는데 이게 자신의 label이 아닐때는? 도착!

label_count : (1,2,3 나눠져있는거 )

 

 

그럼 이때는 이 전 값에서 온 dp값을 출력하면 된다잉

 

어 근데 이거

어디서 많이 봤는데...

 

[DFS,BFS] 백준 7576번 토마토(C++)

[DFS,BFS] 백준 7576번 토마토(C++)

뭔가 토마토 문제하고 비슷하지 않나?

 

여기서 

dp[nx][ny] = dp[nx - dx[i]][ny - dy[i]] + 1;

이런식으로 퍼트려 나갔었고,

각 점에 대해서는 최소인 것이 확정된다고 설명했었다

 

쨋든

 

 

#include <iostream>

#include <vector>

#include <queue>

#include <algorithm>

using namespace std;

queue<pair<int, int>> q;

queue<pair<int, int>> q_label[100];

void bfs(int a, int b);

void bfs_2(int lab_c);

int n;

int dp[100][100] = {0};

int label[100][100] = {0}, label_count = 1;

int arr[100][100];

bool label_visit[100];

bool visited[100][100];

int bridge = 1000000;

int dx[4] = {0, 0, 1, -1};

int dy[4] = {1, -1, 0, 0};

void init()

{

    for (int i = 0; i < n; i++)

    {

        for (int j = 0; j < n; j++)

        {

            // if (label[i][j] == 0)

            visited[i][j] = false;

        }

    }

}

int main()

{

    cin >> n;

    for (int i = 0; i < n; i++)

        for (int j = 0; j < n; j++)

        {

            cin >> arr[i][j];

            if (arr[i][j])

            {

                q.push(make_pair(i, j));

                dp[i][j] = 1;

            }

        }

    for (int i = 0; i < n; i++)

    {

        for (int j = 0; j < n; j++)

        {

            if (!visited[i][j] && arr[i][j])

            {

                bfs(i, j);

                label_count++;

            }

        }

    }

    // for (int i = 0; i < n; i++)

    // {

    //     for (int j = 0; j < n; j++)

    //     {

    //         cout << label[i][j] << " ";

    //     }

    //     cout << "\n";

    // }

    for (int i = 1; i <= label_count; i++)

    {

        init();

        bfs_2(i);

    }

    cout << bridge;

}

void bfs(int a, int b)

{

    queue<pair<int, int>> temp;

    temp.push(make_pair(a, b));

    visited[a][b] = true;

    while (!temp.empty())

    {

        int x = temp.front().first;

        int y = temp.front().second;

        temp.pop();

        label[x][y] = label_count;

        for (int i = 0; i < 4; i++)

        {

            int nx = x + dx[i];

            int ny = y + dy[i];

            if (arr[nx][ny] == 1 && label[nx][ny] == 0 && !visited[nx][ny] && nx < n && nx >= 0 && ny < n && ny >= 0)

            {

                visited[nx][ny] = true;

                label[nx][ny] = label_count;

                temp.push(make_pair(nx, ny));

            }

        }

    }

}

void bfs_2(int lab_c)

{

    queue<pair<int, int>> q_temp;

    for (int i = 0; i < n; i++)

    {

        for (int j = 0; j < n; j++)

        {

            if (label[i][j] == lab_c)

            {

                visited[i][j] = true;

                dp[i][j] = 0;

                q_temp.push(make_pair(i, j));

            }

        }

    }

    while (!q_temp.empty())

    {

        int x = q_temp.front().first;

        int y = q_temp.front().second;

        q_temp.pop();

        for (int i = 0; i < 4; i++)

        {

            int nx = x + dx[i];

            int ny = y + dy[i];

            if (!visited[nx][ny] && nx < n && nx >= 0 && ny < n && ny >= 0)

            {

                visited[nx][ny] = true;

                dp[nx][ny] = dp[x][y] + 1;

                if (label[nx][ny] != 0 && label[nx][ny] != lab_c)

                {

                    bridge = min(bridge, dp[x][y]);

                    return;

                }

                q_temp.push(make_pair(nx, ny));

            }

        }

    }

}

 

풀 코드이다

 

나 이거 풀면서 머리가 빠질뻔했다

 

라벨링 까진 생각해냈는데, 뇌용량을 너무 많이 써서인지 거리구하는게 잘 안구해지더라고 ㅋㅋ

 

다른사람들 풀이를 보면, 섬의 가장자리의 값들을 기준으로 거리를 구햇지만 나같은 경우엔

q값에다가 각 라벨링한 섬의 위치들을 넣고 dp식을 진행해주었다.

 

 

 

 for (int i = 1; i <= label_count; i++)

    {

        init();

        bfs_2(i);

    }

각 라벨 카운팅에 대해 bfs_2 돌려주고

 

if (label[nx][ny] != 0 && label[nx][ny] != lab_c)

이게무슨뜻이냐?

해당 값이 0이 아니고, 또한 자신의 라벨링 값도 아니야.. 그렇다면!!

다른섬에 도착한거겠죠?

 

뭐... 어렵다~