글 읽기 - 11493 틀린경우를 찾고 싶습니다.

wlgns1678 8년 전 0

BFS방식으로 풀어봤는데 기본 테스트 케이스 이외의

직접 작성해 사용한 케이스들이 모두 통과되는데

제출시 2% 중간에서 틀림 으로 나옵니다.

틀린 이유를 찾아야 소스를 수정 할 수 있을텐데 어떤 경우에 틀리는지 잘 모르겠어서 도움을 부탁드립니다.

위와 같은 경우에 3번에 있는 동전이 먼저 1번과 교환되서

2번자리가 4번과 교환하게 되어 3이 나오게 되는 잘못된 경우를 수정하기 위해 우선순위큐를 사용했습니다.

혹시 이문제를 풀면서 이와 같은 틀리게 되는 특별한 케이스를 알려주시면 감사하겠습니다.

import java.util.Iterator;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Scanner;


public class A1 {
	public static void main(String[] args)
	{
		Scanner in = new Scanner(System.in);

		int test_case = in.nextInt();
		for(int i = 0; i < test_case ; i++)
		{
			int point = in.nextInt();    //VertexNum
			int edge = in.nextInt();
			Vertex[] array = new Vertex[point];

			for(int j = 0; j < point; j++)
				array[j] = new Vertex(i);

			for(int j = 0; j < edge; j++) // insert edge
			{
				int from = in.nextInt() -1;
				int to = in.nextInt() -1;   
				array[from].insert(to);
				array[to].insert(from);
			}

			for(int j = 0; j < point; j++)
				array[j].c1 = in.nextInt();
			for(int j = 0; j < point; j++)
				array[j].c2 = in.nextInt();

			int result = 0;
			for(int j = 0; j < point; j++){
				result += find(array, j);  
			}
			System.out.println(result);
		}
	}
	public static int find(Vertex[] array, int index)
	{
		if(array[index].c1 == 0)
			return 0;
		if(array[index].c2 == 1)
			return 0;
		
		PriorityQueue<Vertex> que = new PriorityQueue<>();
		array[index].count = 0;
		que.add(array[index]);
		int[] visit = new int[array.length];
		visit[index] = 1;
		
		while( ! que.isEmpty())
		{
			Vertex curr = que.poll(); 
			
			if(curr.c1 == 0 && curr.c2 == 1){
				curr.c2 = 0;
				return curr.count;
			}
			
			Iterator<Vertex> it = que.iterator();// 시간초과문제를 해결하기 위해 있지만 없어도 무관
			while(it.hasNext())
			{
				Vertex check = it.next();
				if(check.count == curr.count && check.c1 == 0 && check.c2 == 1){
					check.c2 = 0;
					return check.count;
				}
			}
			
			int k = 0;
			while(k < curr.list.size())
			{			
				int next = curr.list.get(k);
				if(visit[next] != 1){
					array[next].count = curr.count + 1;
					que.add(array[next]);
					visit[next] = 1;
				}
				k++;
			}
		}   
		return 1000;
	}
		
}

class Vertex implements Comparable<Vertex>{
	public LinkedList<Integer> list;
	public int vNum;
	public int c1 = 0, c2 = 0;
	public int count = 0;
	public int size = 0;
	public Vertex(int vNum)
	{
		this.vNum = vNum;
		list = new LinkedList<>();
	}
	public void insert(int num)
	{
		list.add(num);
		size++;
	}
	public int compareTo(Vertex other) { 
		if(count > other.count)
			return 1;
		else if(count < other.count)
			return -1;
		else {
			if(size > other.size)
				return 1;
			else if (size < other.size)
				return -1;
			else 
				return 0;
		}
	}
}

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

문제

문제

출처

ICPC

11493 틀린경우를 찾고 싶습니다.

wlgns1678 8년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말