글 읽기 - 자바 로직 관련 문제 입니다. 살려주세요 ㅠㅠ

lee_jaecom 2년 전 0

이 문제 접근 방법입니다.

1. 다익스트라 탐색을 통해 최단경로를 구한다.

2. 1번 다익스트라 경로 추척을 통해 최단경로를 지워준다.

3. 다익스트라 탐색을 한번 더 한다.

4. 2번째 다익스트라 탐색에서 새로운 최단경로가 나왔다면, 그 값이 1번째 다익스트라 값보다 클 경우 해당 값 출력
아닐경우 -1 출력

이런 방법으로 접근했습니다.

게시판 검색, 테케 다 넣어봐도 반례를 못 찾겠습니다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class BJ5719 {
	
	static int N;
	static int[][] roads;
	static final int INF = 1000000000;
	
	static class Trace {
		
		int index; // 다음에 탐색해야할 정점 번호
		int sum; // 이전까지 누적해온 경로비용
		StringBuilder sb; // 경로저장
		
		public Trace(int index, int sum, StringBuilder sb) {
			super();
			this.index = index;
			this.sum = sum;
			this.sb = sb;
		}
		
	}
	
	private static int[] dijkstra(boolean[] visited, int[] distance, int startIdx) {
		distance[startIdx] = 0; // 출발점
		
		for(int i=0; i<N; i++) {
			int index = 0, min = INF;
			for(int j=0; j<N; j++) {
				if(!visited[j] && distance[j] < min) {
					index = j;
					min = distance[j];
				}
			}
			
			for(int j=0; j<N; j++) {
				if(!visited[j] && roads[index][j] != 0) {
					if(distance[j] > distance[index] + roads[index][j]) {
						distance[j] = distance[index] + roads[index][j];
					}
				}
			}
			
			visited[index] = true; // 경유지로 봤으니 방문처리
		}
		return distance;
	}

	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		StringBuilder sb = new StringBuilder();
		
		while(true) {
			st = new StringTokenizer(br.readLine());
			N = Integer.parseInt(st.nextToken());
			int M = Integer.parseInt(st.nextToken());
			
			if(N == 0 && M == 0) break; // 둘 다 0이 들어오면 종료
			
			st = new StringTokenizer(br.readLine());
			int S = Integer.parseInt(st.nextToken());
			int D = Integer.parseInt(st.nextToken());
			
			roads = new int [N][N];
			for(int i=0; i<M; i++) {
				st = new StringTokenizer(br.readLine());
				int U = Integer.parseInt(st.nextToken());
				int V = Integer.parseInt(st.nextToken());
				int P = Integer.parseInt(st.nextToken());
				
				roads[U][V] = P; // 인접행렬로 경로 저장
			}
			
			int[] distance = new int [N];
			Arrays.fill(distance, INF);
			int[] minDistance = dijkstra(new boolean [N], distance, S); // 첫번째 다익스트라 탐색
			
			Queue<Trace> q = new LinkedList<>();
			for(int i=0; i<N; i++) { // 시작점에서 경로가 존재한다면 후보군으로 큐에 등록
				if(roads[S][i] != 0) q.offer(new Trace(i, roads[S][i], new StringBuilder().append(i)));
			}
			
			boolean[][] ischecked = new boolean [N][N]; // 경로 추적을 위한 bfs
			while(!q.isEmpty()) {
				Trace temp = q.poll();
				
				if(temp.index == D && temp.sum == minDistance[D]) {	// 도착지에 도착했고, 누적해온 경로값이 다익스트라 경로값과 같다면 그 경로는 최소경로
					char[] orders = temp.sb.toString().toCharArray(); // S(출발점) 을 제외한 최소경로가 배열로 저장  orders : [ ~ D(도착점) ]
					int prevIdx = S;
					for(int i=0; i<orders.length; i++) {
						int nextIdx = orders[i] - '0';
						roads[prevIdx][nextIdx] = 0; // 경로를 지워준다
						prevIdx = nextIdx;
					}
					continue;
				}
				
				for(int i=0; i<N; i++) { // 후보군이 다음 경로를 탐색할때(1. 경로가 존재하고, 2. 그 경로로 가는 비용이 다익스트라 값보다 작거나 같으면 후보군으로 유지)
					if(roads[temp.index][i] != 0 && temp.sum + roads[temp.index][i] <= minDistance[D] && !ischecked[temp.index][i]) {
						q.offer(new Trace(i, temp.sum + roads[temp.index][i], new StringBuilder().append(temp.sb.toString()).append(i)));
						ischecked[temp.index][i] = true; 
					}
				}
			}
			
			int[] distance2 = new int [N];
			Arrays.fill(distance2, INF);
			int[] nextDistance = dijkstra(new boolean [N], distance2, S); // 2번째 다익스트라 탐색
			
			if(nextDistance[D] != INF && nextDistance[D] > minDistance[D]) sb.append(nextDistance[D]).append("\n"); // 다익스트라를 돌렸을때 새로 찾은 다익스트라가 존재하고 그 값이 이전 다익스트라 보다 크다면
			else sb.append(-1).append("\n"); // 아닐경우
		}
		
		sb.setLength(sb.length()-1);
		System.out.println(sb.toString());
		
	}

}

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

문제

문제

출처

ICPC

자바 로직 관련 문제 입니다. 살려주세요 ㅠㅠ

lee_jaecom 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말