글 읽기 - 고수님들 77%에서 틀렸습니다가 떠요 ㅠㅠ

tjdwo5313 4년 전 0

우선순위가 높은 순으로 MST를 구한 후에 집합의 크기 M을 맞추기 위해 MST에 포함되지 않은 도로 중 우선순위가 높은 도로들을 집합에 포함시키는 방향으로 풀었습니다만

계속해서 77%에서 틀리네요 ㅠㅠㅠ 반례를 들어줄 수 있으신 고수 계신가요 ㅠㅠ

감사합니다..

#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <climits>
#include <set>
#include <cstring>
#include <queue>
#include <map>
#include <functional>
#include <stack>

using namespace std;

#define Fi first
#define Se second
#define endl '\n'

typedef long long ll;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
typedef pair <double, double> pdd;

int parent[50];  // union-find
int cnt[50];  // 도시를 끝점으로 하는 도로의 개수

// find
int root(int city) {
    if (parent[city] == city) {
        return city;
    }
    return parent[city] = root(parent[city]);
}

// union
bool merge(int c_1, int c_2) {
    int r_1 = root(c_1);
    int r_2 = root(c_2);
    if (r_1 != r_2) {
        parent[r_2] = r_1;
        ++cnt[c_1];
        ++cnt[c_2];
        return true;  // merged
    }
    return false;  // not merged
}

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);

    int N, M;
    cin >> N >> M;
    if (N == 1 && M == 0) {  // edge case
        cout << 0 << endl;
        return 0;
    }
    
    vector<pii> roads;
    for (int i = 0; i < N; ++i) {
        bool no_ans = true;
        for (int j = 0; j < N; ++j) {
            char exist;
            cin >> exist;
            if (exist == 'Y') {
                no_ans = false;
                if (j > i) {
                    roads.emplace_back(i, j);  // 우선순위가 높을 수록 먼저 삽입
                }
            }
        }
        if (no_ans) {  // 도시를 연결하는 도로가 없음
            cout << -1 << endl;
            return 0;
        }
    }

    // 도로의 수가 M보다 적음
    if (M > roads.size()) {
        cout << -1 << endl;
        return 0;
    }

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

    vector<pii> lefts;  // MST에 포함되지 않은 도로들
    for (pii r : roads) {
        int c_1 = r.Fi;
        int c_2 = r.Se;
        if (!merge(c_1, c_2)) {
            lefts.emplace_back(c_1, c_2);
        }
    }

    // 높은 우선순위를 갖는 도로들을 집합에 포함시킴
    for (int i = 0; i < M - N + 1; ++i) {
        int c_1 = lefts[i].Fi;
        int c_2 = lefts[i].Se;
        ++cnt[c_1];
        ++cnt[c_2];
    }

    // 정답 출력
    cout << cnt[0];
    for (int i = 1; i < N; ++i) {
        cout << " " << cnt[i];
    }
}

slah007 4년 전 1

92번째 줄에 !merge(c_1, c_2)는 MST에 포함될 필요가 없는 도로인데, merge(c_1, c_2)는 0이라도 MST가 다 만들어진 후에는 추가될 수 있습니다.

!merge(c_1, c_2) 대신 MST에 이 도로가 사용되었는지를 check 해 놓고 그렇지 않은 도로들을 순서대로 봐야할 것 같아요.

tjdwo5313 4년 전 0

답변 주셔서 감사합니다!

답변에 대해 궁금한 점이 있어 댓글을 쓰게 되었는데요~

말씀해주신 "merge(c_1, c_2)는 0이라도 MST가 다 만들어진 후에는 추가될 수 있습니다."

이 부분이 이해가 잘 안되어서요 ㅠㅠ

if (!merge(c_1, c_2)) 를 수행하는 for문이 끝나면 MST에 필요한 N-1개의 도로만 MST에 추가되고

lefts에 담긴 도로들은 MST에 포함되지 않은 도로들이 우선순위에 대해 내림차순으로 정렬된 것이지 않나요?

즉 말씀해주신 "MST에 이 도로가 사용되었는지를 check 해 놓고 그렇지 않은 도로들을 순서대로 봐야할 것 같아요."

이 부분이 잘 구현된 것 아닌지... 싶습니다 ㅠㅠ

slah007 4년 전 1

아 MST를 만들면서 동시에 lefts 배열을 만드네요. 위의 글은 제가 잘못 지적했습니다.

대신에 다른 문제가 되는 부분을 찾았습니다. MST를 만들었을 때 이것이 Connected인지를 검사해야 하는데, 이게 제대로 되지 않습니다.

코드에서는 exist로 Y가 한번이라도 나오면 connected로 만들 수 있다고 가정했는데, 여러 개의 connected graph로 나눠질 경우 성립하지 않습니다.

input:

6 5
NYYNNN
YNYNNN
YYNNNN
NNNNYY
NNNYNY
NNNYYN

output:

-1 (원래 답)

2 1 1 2 1 1 (올리신 코드의 답)

tjdwo5313 4년 전 0

답변 감사합니다 ㅠㅠ

그런 문제가 있었네요..!!

해결해보도록 하겠습니다 ㅠㅠ

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

문제

문제

출처

ICPC

고수님들 77%에서 틀렸습니다가 떠요 ㅠㅠ

tjdwo5313 4년 전 0

slah007 4년 전 1

tjdwo5313 4년 전 0

slah007 4년 전 1

tjdwo5313 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말