글 읽기 - [java] 틀렸습니다가 나옵니다

poj4639 5년 전 1

2차원 int 배열로 풀어봤는데 틀렸습니다가 나오네요.

5,4,3,2,1이 순위일때 5는 (5->4) ,( 5->3 ),( 5->2 ), (5->1) 연결을 가지고, 4는 (4->3),(4->2),(4->1)이런 방식으로 각각 연결을 가지게했습니다

연결을 보내는 쪽은 1로 받는쪽은 -1로 표현했습니다.

5,4,3,2,1인 처음 경우에는 기본적으로 아래 행렬을 가지고

0 -1 -1 -1 -1

1 0 -1 -1 -1

1 1 0 -1 -1

1 1 1 0 -1

1 1 1 1 0

이때 입력받는 순서가 바뀐 쌍들은 예를 들어 (3,4)일 경우에는 4->3이 3->4로 바뀌므로 행렬 (3,4) (4,3)에 각각 -1을 곱해 방향을 바꿔주는 방식으로 표현했습니다. 이때 위상정렬을 이용하여, -1이 없는 행을 탐색하고 만약 -1이 없는 행이 없을경우는 순환이 생긴 경우이므로 impossible을 출력하고 메소드를 return했고, -1이 2개이상인 경우는 순서를 알수 없는 경우이므로 ?를 출력하고 return 시켰습니다. 그리고 하나만 있는경우는 하나를 linkedlist 에 넣고 -1이 없던 행을 전부 -1로 바꿔 다시 탐색되지 않게하고, 그 행에 해당하는 번호의 열을 0으로 바꿔 연결을 제거시킨후, 행의 수만큼 다시 돌아가게 했습니다.

일단 테스트 케이스는 다 맞게 나오는데, 혹시 반례 좀 알려주실수 있으실까요?, 틀렸습니다가 나오네요.

	import java.awt.Point;
	import java.io.BufferedReader;
	import java.io.IOException;
	import java.io.InputStreamReader;
	import java.util.*;
	import java.lang.Long;
import java.math.BigInteger;
	
		public class Main 
		{	
			static int[][] map;
			static int  namenum,pointnum;
			static int[] name;
			static LinkedList k;
			static boolean[][] check;
			public static void main(String args[])
			{
				BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
				int repeat=0;
				try {
					repeat = Integer.parseInt(bf.readLine());
				} catch (NumberFormatException | IOException e) {
					// TODO Auto-generated catch block
					e.printStackTrace();
				}
				for(int re=0;re<repeat;re++)
				{
					try {
						namenum=Integer.parseInt(bf.readLine());
						name = new int[namenum];
						map = new int[namenum][namenum];
						for(int w1=0;w1<namenum;w1++)
						{
							for(int w2=0;w2<namenum;w2++)
							{
								if(w1>w2)
								{
									map[w1][w2]=1;
								}
								else if(w1<w2)
								{
									map[w1][w2]=-1;
								}
								else			
								{
									map[w1][w2]=0;
								}
							}
						}
						String[] s = bf.readLine().split(" ");
						for(int w=0;w<namenum;w++)
						{
							name[namenum-1-w]= Integer.parseInt(s[w]);
						}
						pointnum=Integer.parseInt(bf.readLine());
						for(int i=0;i<pointnum;i++)
						{
							s=bf.readLine().split(" ");
							int a1 = Integer.parseInt(s[0]);
							int a2 = Integer.parseInt(s[1]);
							map[a1-1][a2-1]=map[a1-1][a2-1]*-1;
							map[a2-1][a1-1]=map[a2-1][a1-1]*-1;
						}
						cjs();
					
					} catch (NumberFormatException | IOException e) {
						// TODO Auto-generated catch block
						e.printStackTrace();
					}
				}
					
				
			}
			static void cjs()
			{
				k = new LinkedList();
				for(int aw=0;aw<namenum;aw++)
				{
					int na=0;
				for(int i=0;i<namenum;i++)
				{
					boolean check = true;
					for(int j=0;j<namenum;j++)
					{
						if(map[i][j]==-1)
						{
							check = false;
							break;
						}
					}
					if(check)
					{
						na++;
						k.offerFirst(i);
					}
				}
				if(na==0)
				{
					System.out.println("IMPOSSIBLE");
					return;
				}
				else if(na==1)
				{	
					if(aw==namenum-1)
					{
						while(!k.isEmpty())
						{
							if(k.size()==1)
							{
								System.out.print(name[(int)k.pollLast()]);
								break;
							}
							System.out.print(name[(int) k.pollLast()]+" ");
						}
						System.out.println();
						return;
					}
					
					int sc=(int) k.peek();
					for(int ak=0;ak<namenum;ak++)
						{
						map[sc][ak]=-1;
						map[ak][sc]=0;
					}
				}
				else
				{
					System.out.println("?");
					return;
				}
				}
			}
		}
		
			
		

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