글 읽기 - 비내림차순 입력이 핵심 아닌가요?

kangbada0728 4년 전 0

다른 질문들에도 제가 질문한 내용이 있길래 찾아 봤는데 중간중간 답변들을 삭제해놓아서 이해하기 힘들어 다시 질문을 올립니다.

정점 1부터 bfs 탐색을 돌리며 각 노드의 깊이를 배열에 저장해놓고,

입력 마지막줄의 방문 순서를 차례대로 탐색해보면서 순서가 비내림차순으로 진행되었는지 확인하면 되는줄 알았습니다.

그런데 50% 쯤에 실패가 뜨더군요.

제 접근방식이 왜 잘못됬는지 잘 모르겠습니다.

왜 비내림차순으로 접근하면 안될까요?

#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<stack>
#include<deque>
#include<string>

#include<cstdio>
#include<cstring>
#include<cmath>
#include<climits>

using namespace std;

int N=0;
vector<vector<int>> a(100001);
int v[100001];

class Numbers{
public:
    int n;
    int cnt;
    
    Numbers(int n, int cnt) : n(n), cnt(cnt){}
};

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

    freopen("sample_input.txt", "r", stdin);
    freopen("sample_output.txt", "w", stdout);
    freopen("sample_error.txt", "w", stderr);
    
    cin>>N;
    for(int i=0; i<N-1; ++i){
        int x=0, y=0;
        cin>>x>>y;
        a[x].push_back(y);
        a[y].push_back(x);
    }
    
    queue<Numbers> q;
    q.push(Numbers(1, 1));
    v[1]=1;
    
    while(!q.empty()){
        int n=q.front().n;
        int cnt=q.front().cnt;
        q.pop();
        
        for(int i=0; i<a[n].size(); ++i){
            int nn=a[n][i];
            if(v[nn]==0){
                q.push(Numbers(nn, cnt+1));
                v[nn]=cnt+1;
            }
        }
    }
    
    int n=0;
    int cnt=0;
    for(int i=0; i<N; ++i){
        cin>>n;
        if(v[n]>=cnt){
            cnt=v[n];
        }
        else{
            cout<<0;
            return 0;
        }
    }
    cout<<1;
    return 0;
}

sait2000 4년 전 11

그대로 내신 건 아니시겠죠 파일 입출력을...

아무튼 반례 드립니다. 큐에 2번의 자식인 4 5보다 3번의 자식인 6 7을 먼저 넣으므로 4 5가 6 7보다 먼저 나와서 틀립니다.

in:
7
1 2
1 3
2 4
2 5
3 6
3 7
1 3 2 4 5 6 7

out:
0

kangbada0728 4년 전 1

@sait2000

답변 정말 감사합니다!

3이 2보다 먼저 들어가니깐 당연히 3하고 연결되어 있는 67이 45보다 앞에 나와야 했군요

Queue에 들어가는 순서를 체크하는 것도 중요한지는 미처 생각을 못했네요.

다시한번 감사드립니다 ㅎㅎ

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

문제

문제

출처

ICPC

비내림차순 입력이 핵심 아닌가요?

kangbada0728 4년 전 0

sait2000 4년 전 11

kangbada0728 4년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말