글 읽기 - C++)1차원 배열로 구현했는데 10프로에서 WA로 뜹니다ㅠㅠ

chainjaxx 4년 전 0

1차원 배열로 구현하려고 했습니다.

49번 줄과 같이 입력된 모든 노드가 부모가 없으면 일단 서로를 연결(꼬인 부분이라고 하겠습니다.)하게 했습니다.

그러다가 16번 32번 줄과 같이 1이 입력되면 그때 꼬인 부분을 풀어주어 노드들이 다시 제대로 부모를 향해 가리키도록 했는데요..

(nodeA가 1일 때 nodeB의 부모가 존재한다면 nodeB와 연결된 부분에 꼬인 부분이 있을 것입니다.)

게시판의 글도 읽어보고 제시하신 반례들도 다 돌려봤는데 잘 돌아가는 것 같아서 제출해봐도 10프로에서 WA가 뜨네요..

어떤 부분이 논리적으로 틀렸거나 어떤 조건을 빠뜨린 것 같은데 잘 모르겠습니다..

어느 부분이 잘못됐는 지 확인해주셨으면합니다..

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

int main(void) {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n = 0, nodeA = 0, nodeB = 0;
    cin >> n;
    stack<int> s;
    
    int *parent = new int[n + 1]();
    parent[0] = 1;
    parent[1] = 1;
    for (int i = 1; i < n; i++) {
        cin >> nodeA >> nodeB;
        if (nodeA == 1) {
            int ptr = nodeB;
            if (parent[nodeB]) { // nodeA가 루트인데 nodeB가 부모가 있다면
                while (parent[parent[ptr]] != ptr) { // 꼬인 부분 만날 때까지 ptr 이동 및 저장
                    s.push(ptr);
                    ptr = parent[ptr];
                }
                while (!s.empty()) { // 가리키는 방향을 반대로 돌려 줌 (부모가 자식을 가리키도록)
                    int top = s.top();
                    s.pop();
                    parent[ptr] = top;
                    ptr = top;
                }
            }
            parent[ptr] = nodeA;
        }
        else if (nodeB == 1) {
            int ptr = nodeA;
            if (parent[nodeA]) {
                while (parent[parent[ptr]] != ptr) { // 꼬인 부분 만날 때까지
                    s.push(ptr);
                    ptr = parent[ptr];
                }
                while (!s.empty()) {
                    int top = s.top();
                    s.pop();
                    parent[ptr] = top;
                    ptr = top;
                }
            }
            parent[ptr] = nodeB;
        }
        else if (!parent[nodeA]) {
            if (!parent[nodeB]) { // 둘다 부모가 없으면 일단 서로를 연결(꼬인 부분)
                parent[nodeA] = nodeB;
                parent[nodeB] = nodeA;
            }
            parent[nodeA] = nodeB;
        }
        else {
            parent[nodeB] = nodeA;
        }

    }
    for (int i = 2; i <= n; i++) {
        cout << parent[i] << "\n";
    }
    return 0;
}

chainjaxx 4년 전 0

생각하다 보니

1 2

4 5

3 4

7 8

6 7

5 6

2 3

이런 식으로 입력되면 답이 이상하게 나오네요..

1차원 배열로 풀고 싶은 데 혹시라도 아시면 알려주시면 감사하겠습니다ㅠㅠ

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

문제

문제

출처

ICPC

C++)1차원 배열로 구현했는데 10프로에서 WA로 뜹니다ㅠㅠ

chainjaxx 4년 전 0

chainjaxx 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말