글 읽기 - 테스트 케이스하고 반례는 다 맞게 뜨는데 힌트좀 얻을 수 있을까요?

ckck803 4년 전 0

다른 분들이 올리신 테스트 케이스하고 반례하고 다 돌려봤는데 계속 4%에서 틀렸다고 뜨네요. ㅠㅠ

어디서 문제가 있어서 틀리는 걸까요?

#include <algorithm>
#include <iostream>
#include <queue>
using namespace std;

#define INF 987654321

int N, M;
int map[11][11];
int colorMap[11][11];
int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};
int bridge[10][10];
int parent[10];

struct point {
    int y;
    int x;
    int num;
};

struct edge {
    int from;
    int to;
    int weight;
};


queue<point> search_bfs(int y, int x, int area) {
    vector<vector<bool>> check(N, vector<bool>(M, false));
    queue<pair<int, int>> q;
    queue<point> local;

    q.push({y, x});
    local.push({y, x, 0});
    check[y][x] = true;

    while (!q.empty()) {
        int cntY = q.front().first;
        int cntX = q.front().second;
        q.pop();

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

            if (0 <= ny && ny < N && 0 <= nx && nx < M) {
                if (check[ny][nx] == false && map[ny][nx] == 1 && colorMap[ny][nx] == area) {
                    check[ny][nx] = true;
                    q.push({ny, nx});
                    local.push({ny, nx, 0});
                }
            }
        }
    }

    return local;
}

// 세로로 다리 놓기
void cero_bfs(int y, int x, int area) {
    vector<vector<bool>> check(N, vector<bool>(M, false));
    queue<point> q = search_bfs(y, x, area);
    check[q.front().y][q.front().x] = true;

    while (!q.empty()) {
        int cntY = q.front().y;
        int cntX = q.front().x;
        int cntNum = q.front().num;
        q.pop();

        if (map[cntY][cntX] == 1 && colorMap[cntY][cntX] != area) {
            if (cntNum - 1 > 1) {
                int from = area;
                int to = colorMap[cntY][cntX];

                if (bridge[from][to] > cntNum) {
                    bridge[from][to] = cntNum - 1;
                    bridge[to][from] = cntNum - 1;
                }
            }
            continue;
        }
        for (int i = 2; i < 4; i++) {
            int ny = cntY + dy[i];
            int nx = cntX + dx[i];

            if (0 <= ny && ny < N && 0 <= nx && nx < M) {
                if (check[ny][nx] == false && colorMap[ny][nx] != area) {
                    check[ny][nx] = true;
                    q.push({ny, nx, cntNum + 1});
                }
            }
        }
    }
}

// 가로로 다리 놓기
void garo_bfs(int y, int x, int area) {
    vector<vector<bool>> check(N, vector<bool>(N, false));
    queue<point> q = search_bfs(y, x, area);
    check[q.front().y][q.front().x] = true;

    while (!q.empty()) {
        int cntY = q.front().y;
        int cntX = q.front().x;
        int cntNum = q.front().num;
        q.pop();

        if (map[cntY][cntX] == 1 && colorMap[cntY][cntX] != area) {
            if (cntNum - 1 > 1) {
                int from = area;
                int to = colorMap[cntY][cntX];

                if (bridge[from][to] > cntNum) {
                    bridge[from][to] = cntNum - 1;
                    bridge[to][from] = cntNum - 1;
                }
            }
            continue;
        }

        for (int i = 0; i < 2; i++) {
            int ny = cntY + dy[i];
            int nx = cntX + dx[i];

            if (0 <= ny && ny < N && 0 <= nx && nx < M) {
                if (check[ny][nx] == false && colorMap[ny][nx] != area) {
                    check[ny][nx] = true;
                    q.push({ny, nx, cntNum + 1});
                }
            }
        }
    }
}

void color_bfs(int y, int x, int area) {
    vector<vector<bool>> check(N, vector<bool>(N, false));
    queue<pair<int, int>> q;
    q.push({y, x});
    check[y][x] = true;
    colorMap[y][x] = area;

    while (!q.empty()) {
        int cntY = q.front().first;
        int cntX = q.front().second;
        q.pop();

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

            if (0 <= ny && ny < N && 0 <= nx && nx < M) {
                if (colorMap[ny][nx] == 0 && check[ny][nx] == false && map[ny][nx] == 1) {
                    colorMap[ny][nx] = area;
                    check[ny][nx] = true;
                    q.push({ny, nx});
                }
            }
        }
    }
}

bool cmp(edge a, edge b) {
    return a.weight < b.weight;
}
int find(int x) {
    if (x == parent[x]) {
        return x;
    } else {
        return parent[x] = find(parent[x]);
    }
}
void merge(int a, int b) {
    int set_a = parent[a];
    int set_b = parent[b];

    parent[set_a] = set_b;
}

int main(void) {
    cin >> N >> M;

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

    for (int i = 0; i < 10; i++) {
        for (int j = 0; j < 10; j++) {
            bridge[i][j] = INF;
        }
    }

    int color = 0;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            if (map[i][j] == 1 && colorMap[i][j] == 0) {
                color++;
                color_bfs(i, j, color);
            }
        }
    }

    vector<bool> area_check(color, false);
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            int cntColor = colorMap[i][j];
            if (map[i][j] == 1 && !area_check[cntColor]) {
                area_check[cntColor] = true;
                cero_bfs(i, j, cntColor);
                garo_bfs(i, j, cntColor);
            }
        }
    }

    vector<edge> edges;
    for (int i = 1; i <= color; i++) {
        for (int j = i + 1; j <= color; j++) {
            if (bridge[i][j] != INF) {
                // cout << i << " " << j << " " << bridge[i][j] << endl;
                edges.push_back({i, j, bridge[i][j]});
            }
        }
    }

    sort(edges.begin(), edges.end(), cmp);

    for (int i = 0; i < 10; i++) {
        parent[i] = i;
    }

    int i = 0;
    int cnt = 0;
    int sum = 0;
    while (cnt != color - 1 && i < edges.size()) {
        int a = edges[i].from;
        int b = edges[i].to;

        if (find(a) != find(b)) {
            merge(a, b);
            cnt++;
            sum += edges[i].weight;
        }
        i++;
    }

    if (cnt == color - 1) {
        cout << sum << '\n';
    } else {
        cout << -1 << '\n';
    }
    return 0;
}

9967han 4년 전 0

어떻게 해결하셨나요? ㅠㅠ

ckck803 4년 전 0

1. check 백터 배열을 n * m으로 잡았어야 했는데 n*n으로 잡아서 오류가 떳었어요!

2. if(bridge[from][to] > cntNum) cntNum - 1을 비교했어야 했는데 cntNum으로 비교 해서 틀렸었어요

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

테스트 케이스하고 반례는 다 맞게 뜨는데 힌트좀 얻을 수 있을까요?

ckck803 4년 전 0

9967han 4년 전 0

ckck803 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말