글 읽기 - 어느부분이 틀렸는지 알려주시면 감사하겠습니다~:)

ugs1575 3년 전 1

반례를 못 찾아서 헤매고 있습니다

어떤 반례가 있을까요??

import java.util.*;

public class Main {
    static ArrayList<Integer>[] aList; //노드 저장
    static int[] check; //방문 여부 체크
    static int[] visitOrder; //방문 순서 저장배열
    static int result = 1;
    public static void main(String args[]){
        Scanner sc = new Scanner(System.in);
        int nodeCnt = sc.nextInt();
        aList = new ArrayList[nodeCnt+1];
        check = new int[nodeCnt+1];
        visitOrder = new int[nodeCnt];

        for(int i=1; i<=nodeCnt; i++){
            aList[i] = new ArrayList<Integer>();
        }

        for(int i=0; i<nodeCnt-1; i++){
            int from = sc.nextInt();
            int to = sc.nextInt();
            aList[from].add(to);
            aList[to].add(from);
        }
        
        for(int i=0; i<nodeCnt; i++){
            int n = sc.nextInt();
            //방문순서가 항상 1이니까, 입력 방문순서 첫번째값이 1이 아니면 0 출력
            if(i == 0 && n != 1){
                result = 0;
                break;
            }
            
            visitOrder[i] = n;
        }
        
        if(result != 0){
            bfs(1);
        }
       

        System.out.println(result);
    }

    public static void bfs(int n){
        Queue<Integer> q = new LinkedList<Integer>();
        q.add(n);
        check[n] = 1;
        int j = 1; //입력 방문순서 검사 시작 인덱스

        while (!q.isEmpty()){
            int parent = q.remove();
            int size = 0;
            for(int i=0; i<aList[parent].size(); i++){
                int next = aList[parent].get(i);
                if(check[next] == 0){
                    size++;
                    q.add(next);
                    check[next] = parent; //부모값을 넣어줌
                }
            }
            //큐에 들어온 자식노드갯수만큼 방문배열을 검사
            for(int i=j; i<j+size; i++){
                //방문 배열의 부모값이 pop한 노드의 값과 다르거나 방문한 값이 아니면
                if(check[visitOrder[i]] != parent || check[visitOrder[i]] == 0){
                    result = 0;
                }
            }
            
            j = j+size;

        }
    }

}

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

문제

문제

출처

ICPC

어느부분이 틀렸는지 알려주시면 감사하겠습니다~:)

ugs1575 3년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말