2146 다리 만들기

문제 링크

• 풀이

전체 맵을 순환하며 섬의 테두리를 BFS를 통해 찾고 테두리에서 해당 섬에서 다른 섬 까지의 최단 거리를 BFS를 통해 찾아 반환한다. DFS도 사용 된다고 했는데 어디있는지 잘 모르겠다.

#define _CRT_SECURE_NO__WARNINGS

#include <iostream>
#include <queue>
#include <algorithm>
#include <cstring>

using namespace std;

int N, island;
int m[102][102], t[102][102];
int dis[102][102];
int dr[4] = { -1, 1, 0, 0 };
int dc[4] = { 0,  0, -1, 1 };

struct BorderPoint
{
    int row, col, dis;
    
    BorderPoint(int r, int c, int d) : row(r), col(c), dis(d) {}
};

int bfs()
{
    deque<pair<int, int>> q;
    deque<BorderPoint> bq;
    vector<BorderPoint> border;
    int ret = 987654321;

    for (int r = 1; r <= N; r++) for (int c = 1; c <= N; c++)
    {
        if (m[r][c] == 1)
        {
            q.push_back(make_pair(r, c));
            m[r][c] = island;

            while (!q.empty())
            {
                bool isBorder = false;
                int rr = q.front().first;
                int cc = q.front().second;
                q.pop_front();

                for (int d = 0; d < 4; d++)
                {
                    int nr = rr + dr[d];
                    int nc = cc + dc[d];

                    if (m[nr][nc] != 1)
                    {
                        if (m[nr][nc] == 0)
                            isBorder = true;
                        continue;
                    }

                    m[nr][nc] = island;
                    q.push_back({ nr, nc });
                }

                if (isBorder)
                    border.push_back({ rr, cc, 0 });
            }

            while (!border.empty())
            {
                bq.push_back({ border.back().row, border.back().col, border.back().dis });
                border.pop_back();
                memcpy(t, m, sizeof(m));

                while (!bq.empty())
                {
                    int br = bq.front().row;
                    int bc = bq.front().col;
                    int bd = bq.front().dis;
                    bq.pop_front();

                    if (bd > ret)
                    {
                        bq.clear();
                        continue;
                    }

                    for (int d = 0; d < 4; d++)
                    {
                        int newBr = br + dr[d];
                        int newBc = bc + dc[d];

                        if (t[newBr][newBc] == -1 || t[newBr][newBc] == island)
                            continue;

                        if (t[newBr][newBc] != 0)
                        {
                            if (bd < ret)
                                ret = bd;
                            bq.clear();
                        }
                        else
                        {
                            t[newBr][newBc] = island;
                            bq.push_back({ newBr, newBc, bd + 1 });
                        }
                    }
                }
            }
            island += 1;
        }
    }

    return ret;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    cin >> N;
    for (int r = 1; r <= N; r++) for (int c = 1; c <= N; c++)
        cin >> m[r][c];

    for (int i = 0; i <= N; i++)
    {
        m[0][i] = -1;
        m[N + 1][i] = -1;
        m[i][0] = -1;
        m[i][N + 1] = -1;
    }

    island = 2;

    cout << bfs() << "\n";
}

• 다른 사람 풀이

#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <queue>

#define INF (int)2e9

using namespace std;

void dfs(int, int);
int bfs(void);

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

int N, G, A[102][102];
int visited[102][102];
bool check[102][102];

int main(void)
{
    scanf("%d", &N);

    for (int i = 1; i <= N; i++)
        for (int j = 1; j <= N; j++)
            scanf("%d", &A[i][j]);

    for (int i = 1; i <= N; i++)
        for (int j = 1; j <= N; j++)
            if (A[i][j] && !check[i][j])
                G++, dfs(i, j);
    
    printf("%d\n", bfs());

    return 0;
}

void dfs(int x, int y)
{
    check[x][y] = true;
    A[x][y] = G;

    for (int i = 0; i < 4; i++) {
        int nx = x + dx[i];
        int ny = y + dy[i];

        if (A[nx][ny] && !check[nx][ny])
            dfs(nx, ny);
    }
}

int bfs(void)
{
    queue<pair<int, int>> Q;

    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            if (A[i][j])
                visited[i][j] = 0, Q.push(make_pair(i, j));
            else
                visited[i][j] = INF;
        }
    }

    int ret = INF;

    while (!Q.empty()) {
        int curx = Q.front().first;
        int cury = Q.front().second;
        Q.pop();

        for (int i = 0; i < 4; i++) {
            int nx = curx + dx[i];
            int ny = cury + dy[i];

            if (A[nx][ny] && A[curx][cury] != A[nx][ny])
                ret = min(ret, visited[curx][cury] + visited[nx][ny]);

            if (visited[nx][ny] == INF) {
                A[nx][ny] = A[curx][cury];
                visited[nx][ny] = visited[curx][cury] + 1;
                Q.push(make_pair(nx, ny));
            }
        }
    }

    return ret;
}

• if문 안에 ‘,‘를 이용해서 한 줄로 두 줄을 썼네 신기하네!