17472번 다리 만들기 2

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

 

 

오랜만에 풀어보았는데, 계속 오답이 출력됐다.

 

이유는 bfs의 로직때문이었는데, 수정하지 통과됐다.

 

 

잘못된 bfs 로직

// →
            if (k == 0) {
                if (c + 1 < C && !vis[r][c + 1][k] && (g[r][c + 1] == 0 || g[r][c + 1] == e)) {
                    if (g[r][c + 1] == e && g[r][c] == e) {
                        continue;
                    }
                    vis[r][c + 1][k] = true;
                    q.push({ k, {r, c + 1} });
                }
            }
            // ↓
            else if (k == 1) {
                if (r + 1 < R && !vis[r + 1][c][k] && (g[r + 1][c] == 0 || g[r + 1][c] == e)) {
                    if (g[r + 1][c] == e && g[r][c] == e) {
                        continue;
                    }
                    vis[r + 1][c][k] = true;
                    q.push({ k, {r + 1, c} });
                }
            }
            // ←
            else if (k == 2) {
                if (c - 1 > 0 && !vis[r][c - 1][k] && (g[r][c - 1] == 0 || g[r][c - 1] == e)) {
                    if (g[r][c - 1] == e && g[r][c] == e) {
                        continue;
                    }
                    vis[r][c - 1][k] = true;
                    q.push({ k, {r, c - 1} });
                }
            }
            // ↑
            else if (k == 3) {
                if (r - 1 > 0 && !vis[r - 1][c][k] && (g[r - 1][c] == 0 || g[r - 1][c] == e)) {
                    if (g[r - 1][c] == e && g[r][c] == e) {
                        continue;
                    }
                    vis[r - 1][c][k] = true;
                    q.push({ k, {r - 1, c} });
                }
            }

 

 

 

정답 코드

#include <bits/stdc++.h>

using namespace std;

#define MAX 11
#define INF 1000000

int R, C, p[MAX], m[MAX][MAX], g[MAX][MAX];
int dy[4] = { 0, 1, 0, -1 };
int dx[4] = { 1, 0, -1, 0 };
vector<pair<int, pair<int, int>>> v;
bool used[MAX][MAX], vis[MAX][MAX][4];

queue<pair<int, pair<int, int> > > makeQueueAndUsed(int s) {
    queue<pair<int, pair<int, int> > > q;

    for (int i = 0; i < R; i++) {
        for (int j = 0; j < C; j++) {
            if (g[i][j] == s) {
                for (int k = 0; k < 4; k++) {
                    q.push({ k, {i, j} });
                    vis[i][j][k] = true;
                }
            }
        }
    }

    return q;
}

int bfs(int s, int e) {

    memset(vis, false, sizeof(vis));
    queue<pair< int, pair<int, int> > > q = makeQueueAndUsed(s);

    int ret = 0;

    while (!q.empty()) {
        int qs = q.size();

        while (qs--) {
            int k = q.front().first;
            int r = q.front().second.first;
            int c = q.front().second.second;
            
            q.pop();

            int y = r + dy[k];
            int x = c + dx[k];

            if (y < 0 || y >= R || x < 0 || x >= C || vis[y][x][k]) {
                continue;
            }

            if (g[y][x] == e && ret >= 2) {
                return ret;
            }

            if (g[y][x] == 0) {
                vis[y][x][k] = true;
                q.push({ k, {y, x} });
            }
        }

        ++ret;
    }

    return -1;
}

void dfs(int r, int c, int group_number) {

    used[r][c] = true;
    g[r][c] = group_number;

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

        if (y < 0 || y >= R || x < 0 || x >= C || used[y][x] || m[y][x] == 0) {
            continue;
        }

        dfs(y, x, group_number);
    }
}

int Find(int x) {
    if (x == p[x]) {
        return x;
    }
    return p[x] = Find(p[x]);
}

void Union(int a, int b) {
    a = Find(a);
    b = Find(b);

    if (a < b) {
        p[b] = a;
    }
    else {
        p[a] = b;
    }
}

int main()
{
    cin.tie(0);

    for (int i = 0; i < MAX; i++) {
        p[i] = i;
    }

    scanf("%d %d", &R, &C);

    for (int i = 0; i < R; i++) {
        for (int j = 0; j < C; j++) {
            scanf("%d", &m[i][j]);
        }
    }

    // 1. grouping(dfs)
    int group_number = 1;
    for (int i = 0; i < R; i++) {
        for (int j = 0; j < C; j++) {
            if (m[i][j] == 1 && !used[i][j]) {
                dfs(i, j, group_number);
                ++group_number;
            }
        }
    }

    --group_number;

    // 2. bfs
    for (int i = 1; i <= group_number; i++) {
        for (int j = i + 1; j <= group_number; j++) {
            int dist = bfs(i, j);
            //printf("[%d] → [%d] = %d\n", i, j, dist);
            if (dist >= 2) {
                v.push_back({ dist, {i, j} });
            }
        }
    }

    // 3. mst
    sort(v.begin(), v.end());

    int cnt = 0, sum = 0;
    for (auto i : v) {
        int dist = i.first;
        int a = i.second.first;
        int b = i.second.second;

        if (Find(a) != Find(b)) {
            Union(a, b);
            sum += dist;
            if (++cnt == group_number - 1) {
                break;
            }
        }
    }

    printf("%d\n", cnt == group_number - 1 ? sum : -1);

    return 0;
}