글 읽기 - 어디서 논리적인 문제가 발생한건지 모르겠습니다.

hpdong413 7년 전 0

먼저 각 팀을 정점으로 표현한 뒤, 등수가 높은 팀이 등수가 낮은 팀을 일일이 가리키는 형태로 그래프를 표현했습니다.

그 다음 순위가 바뀐 두 정점과 관련하여 기존에 존재하던 간선 방향을 뒤바꿨습니다.

또한 위상 정렬 기능을 구현하기 위해 만들어 놓은 indegrees 배열(각 정점으로 들어오는 간선의 수) 역시 그에 맞게 수정했습니다.

그런데 25%까지만 진행되고 문제가 해결되지 않더라구요ㅠㅠ 어디에서 논리적인 오류가 발생한 건지 모르겠습니다.

문제에 대한 정답 코드를 인터넷에서 찾아보고 실행도 해본 뒤, 응용해서 코드를 작성했는데 잘 동작하지 않네요....

논리적인 오류가 발생한 부분이나 코딩 과정에서의 비효율적인 부분 등에 대해 조언좀 해주시면 감사하겠습니다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Scanner;

public class Main {
	
	public static void main(String[] args) throws IOException {
	        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
	        Scanner sc = new Scanner(in);
	        int T = sc.nextInt();
	        
	        for (int t = 0; t < T; t++) {
	        	int V = sc.nextInt();
	        	int[] numArr = new int[V];
	        	for (int i = 0; i < V; i++) {
	        		numArr[i] = sc.nextInt();
	        	}
	        	
	        	int[] indegrees = new int[V + 1];
	        	List<List<Integer>> adjList = new ArrayList<>(V + 1);
	        	for (int v = 0; v <= V; v++) {
	        		adjList.add(new LinkedList<>());
	        	}
	        	
	        	for (int i = 0; i < V; i++) {
	        		int source = numArr[i];
	        		for (int j = i + 1; j < V; j++) {
	        			int target = numArr[j];
	        			adjList.get(source).add(target);
	        			indegrees[target]++;
	        		}
	        	}
	        	
	        	int M = sc.nextInt();
	        	for (int m = 0; m < M; m++) {
	        		int source = sc.nextInt();
	        		int target = sc.nextInt();
	        		
	        		adjList.get(target).remove((Integer)source);
	        		indegrees[source]--;
	        		adjList.get(source).add(target);
	        		indegrees[target]++;
	        	}
	        	
	        	Queue<Integer> queue = new LinkedList<>();
	        	for (int v = 1; v <= V; v++) {
	        		if (indegrees[v] == 0)
	        			queue.add(v);
	        	}
	        	
	        	boolean isImpossible = false;
	        	boolean isAmbiguous = false;
	        	
	        	int[] result = new int[V + 1];
	        	for (int v = 1; v <= V; v++) {
	        		
	        		if (queue.isEmpty()) {
	        			isImpossible = true;
	        			break;
	        		}
	        		
	        		if (queue.size() > 1) {
	        			isAmbiguous = true;
	        			break;
	        		}
	        		
	        		int source = queue.remove();
	        		result[v] = source;
	        		for (int target : adjList.get(source)) {
	        			if (--indegrees[target] == 0)
	        				queue.add(target);
	        		}
	        	}
	        	
	        	if (isImpossible) {
	        		System.out.println("IMPOSSIBLE");
	        	} 
	        	else if (isAmbiguous) {
	        		System.out.println("?");
	        	}
	        	else {
	        		for (int v = 1; v <= V; v++) 
	        			System.out.print(result[v] + " ");
	        		System.out.println();
	        	}
	        }
	}
}

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

문제

문제

출처

ICPC

어디서 논리적인 문제가 발생한건지 모르겠습니다.

hpdong413 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말