글 읽기 - 2644번 문제 어디가 틀렸는지 모르겠습니다.ㅠㅠ 반례좀 찾아주세요

jarneg23 5년 전 0

child와 parent를 가지는 Node 를 만들어 아래로 전부 탐색 후 목표로 하는 값이 있으면 그 깊이를 출력

목표로하는 값이 없으면 parent로 올라가서 다시 parent 아래로 전부 탐색 한다.

root 까지 올라 갔는데 목표 값이 없으면 -1을 출력하고

목표로 하는 값이 있으면 parent에서 목표 값 까지의 깊이에 기존의 값에서 parent로 올라간 깊이를 합하여 출력한다.

라는 방식으로 했는데 질문 게시판에 있는 반례들과 테스트케이스 모두 통과가 되는데 결과는 틀렸습니다가 나오네요 .ㅠㅠ 반례좀 찾아주세요 ㅠㅠ

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Scanner;

class node
{
	int parent;
	List<Integer> child;
	boolean flag;
	node(){parent = 0; child = new ArrayList<Integer>(); flag = false;}
}

class Search
{
	node[] items;
	Queue<Integer> que = new LinkedList<Integer>();
	Search(node[] item){items = item;}
	
	int calResult(int target1, int target2)
	{
		
		while(items[target1].child.size() >0)
		{
			int tmp = items[target1].child.get(0);
			if(tmp == target2) return 1;
			if(items[tmp].child.size() !=0)
			{
				que.offer(tmp);
				items[target1].child.remove(0);
			}
			else
			{
				items[target1].child.remove(0);
			}
		}
		
		while(que.size() >0)
		{
			int tmp = calResult(que.poll(),target2);
			if(tmp != 0) 
				{
				 	
				 	return tmp +1;
				}
		}
		
		return 0;
	}
	
}

public class back_2644 {
	public static void main(String[] args) 
	{
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt(); // 사람 수
		int 	target1 = sc.nextInt();
		int target2 = sc.nextInt();
		int m = sc.nextInt();//관계수
		node[] bfs = new node[n+1];
		
		for(int i=0; i<n+1; i++)
		{
			bfs[i] = new node();
		}
		
		for(int i=0; i<m; i++)
		{
			int parent = sc.nextInt();
			int child = sc.nextInt();
			if(parent != child)
			{
			bfs[child].parent = parent;
			bfs[parent].child.add(child);
			}
		}
		
		if(target1 == target2)
		{
			System.out.println(0);
			
		}else
		{
			Search _bfs = new Search(bfs);
			int result = 0;
			int count = 0;
			
			result = _bfs.calResult(target1, target2);
			
			while(result == 0 && bfs[target1].parent != 0 )
			{
				target1 = bfs[target1].parent;
				count++;
				
				result = _bfs.calResult(target1, target2);
			}
			
			
			if(result == 0) {System.out.println("-1");}
			else {
			System.out.println(result + count);
			}
		}
		
		
}

}

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

문제

문제

출처

ICPC

2644번 문제 어디가 틀렸는지 모르겠습니다.ㅠㅠ 반례좀 찾아주세요

jarneg23 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말