글 읽기 - 16402번 문제 "제국" 질문드립니다.

todory2002 4년 전 0

문제를 읽으니 유니온 파인드 문제인거 같아서 전형적인 유니온파인드 코드를 작성했습니다. 문제에서 주어진 조건들도 다 고려했습니다.

(종주국 vs 타 종주국 / 종주국 vs 타 종주국의 속국 / 종주국 vs 자신의 속국)

출력까지 ASCII 오름차순으로 잘 출력한 것 같은데, 왜인지 채점하면 1%에서 바로 틀렸습니다 가 나옵니다.

코드 설명을 조금 해보자면, Find 함수는 말 그대로 매개변수의 최상단 부모를 리턴해줍니다. 아울러 재귀를 통해 찾는 과정에서, 최상단 부모와 2단계 이상 멀어진 상태로 이어져있는 노드를 최상단 부모의 직계자식으로 만들어줍니다.

전쟁 상태를 처리할 때, 종주국 vs 자신의 속국 경우가 예외적이라 이 경우만 if문을 통해 처리해주고 이외의 경우는 기본적인 Union 하는 방법을 따랐습니다.

유니온 파인드 코드를 제가 잘못 짠건지 모르겠어서 질문드립니다. 고수분들 도와주시면 정말로 감사하겠습니다ㅠ

#include <bits/stdc++.h>
using namespace std;

vector<string> nations;
vector<int> parent;
int n,m;

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

int main(void) {
    cin.sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    cin >> n >> m; cin.ignore();
    nations.resize(n);
    for(int i=0; i<n; ++i) {
        string temp;
        getline(cin, temp);
        nations[i] = temp.substr(11, temp.length());
    }

    sort(nations.begin(), nations.end());

    parent.resize(n);
    for(int i=0; i<n; ++i) parent[i] = i;

    for(int i=0; i<m; ++i) {
        string temp;
        getline(cin, temp);
        
        string n1;
        int index=11;
        while(temp[index] != ',') { n1 += temp[index++]; } 
        
        string n2;
        index += 12;
        while(temp[index] != ',') { n2 += temp[index++]; }
        
        int res = temp[index+1]-'0';

        int n1Index = lower_bound(nations.begin(), nations.end(), n1)-nations.begin();
        int n2Index = lower_bound(nations.begin(), nations.end(), n2)-nations.begin();

        int n1p = Find(n1Index);
        int n2p = Find(n2Index);

        // 속국이 자신의 종주국 공격
        if(n1p == n2p) {
            int owner = n1p == n1Index ? n1Index : n2Index;

            if(n2Index == owner && res == 1) {
                parent[n2Index] = n1Index;
                parent[n1Index] = n1Index;
            } else if(n1Index == owner && res == 2) {
                parent[n1Index] = n2Index;
                parent[n2Index] = n2Index;
            }
        }
        else {
            if(res == 1) parent[n2Index] = n1Index;
            else parent[n1Index] = n2Index;
        }
    }

    vector<string> ans;
    for(int i=0; i<n; ++i) {
        if(i == parent[i]) ans.push_back(nations[i]);
    }

    printf("%d\n", ans.size());
    for(int i=0; i<ans.size(); ++i) {
        printf("Kingdom of %s\n", ans[i].c_str());
    }
}

minjoonist 4년 전 0

cin.sync_with_stdio(false);

는 C와 C++ 버퍼의 동기화를 끊기 때문에 C문법과 C++문법을 섞어 쓰면 안 되는 것으로 알고 있습니다.

아예 scanf 과 printf 로 하던지 아니면 cin cout 으로 해야 합니다.

todory2002 4년 전 0

@minjoonist 어이없는 실수를 했네요.. ㅠㅠ 63, 64번 째 줄에도 문제가 있어서 말씀해주신 부분이랑 이 부분 고쳤더니 맞았습니다 나왔습니다. 감사합니다.

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