글 읽기 - 어떤 부분을 놓쳤을까요? ㅜㅜ (java)

hyunjunge 2년 전 0

예시의 결과는 구했지만 틀렸다고 합니다ㅠ

어떤 부분을 놓쳤을까요?

로직의 흐름은 아래와 같습니다.

1. 최단경로를 구한다 (dijkstra 함수)

2. 경로를 확인하기 위해서 역추적을 사용(trace함수)

최단경로 = 그 전 도시의 최단경로 + cost 가 성립하면 그 도시를 통과했다고 판단 (bfs 방식 이용)

조언해 주시면 감사하겠습니다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.StringTokenizer;


public class Main {

	private static class Node {
		int dest;
		int cost;
		
		public Node (int dest, int cost) {
			this.dest = dest;
			this.cost = cost;
		}
	}
	
	private static int N; // 도시의 개수
	private static int M; // 버스의 개수
	
	private static ArrayList<Node>[] adjList; // 버스노선을 담을 인접리스트
	private static ArrayList<Node>[] adjList_rev; // 버스노선을 담을 인접리스트
	
	private static int[] dist; // 최단거리를 담을 경로
	
	private static boolean[] visited;
	private static int count; // 최단거리의 개수

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		StringTokenizer st = new StringTokenizer(br.readLine());		
		N = Integer.parseInt(st.nextToken());
		
		st = new StringTokenizer(br.readLine());		
		M = Integer.parseInt(st.nextToken());
		
		adjList = new ArrayList[N+1];
		adjList_rev = new ArrayList[N+1];
		
		for (int i=1; i<=N; i++) {
			adjList[i] = new ArrayList<>();
			adjList_rev[i] = new ArrayList<>();
		}
		
		for (int i=1; i<=M; i++) {
			st = new StringTokenizer(br.readLine());
			
			int start = Integer.parseInt(st.nextToken());
			int end = Integer.parseInt(st.nextToken());
			int cost = Integer.parseInt(st.nextToken());
			
			// 1->5까지 최소 비용
			adjList[start].add(new Node(end, cost));
			// 역방향
			adjList_rev[end].add(new Node(start, cost));
		}
		
		
		st = new StringTokenizer(br.readLine());		
		int A = Integer.parseInt(st.nextToken());
		int B = Integer.parseInt(st.nextToken());
		
		// 우선 최단 경로를 구해서
		dist = new int[N+1];
		
		dijkstra(A, B);
		
		// 최단 경로의 값을 이용하여 경로를 역추적하자
		count = 0;
		visited = new boolean[N+1];
		
		ArrayList<Integer> result = trace(B, A);
		
		System.out.println(dist[B]);
		
		// 출발/도착도시를 포함한 최단경로를 만드는 도시의 개수
		System.out.println((count));
		
		// 도시의 경로 출력		
		for(int i=result.size()-1; i>=0; i--) {
			System.out.print(result.get(i) +" ");
		}
	}

	// 최단 거리를 가기까지 경로를 찾으려면
	// 내가 이미 아는것은 최단 경로들의 합
	// 도착점부터 인접한 정점들을 탐색하면서, 경로의 합과 일치하면 값을 넣어줌
	// 역방향 탐색이니까 헷갈리지 말 것
	private static ArrayList<Integer> trace(int startCity, int endCity) {
		// 결과물을 담을 ArrayList
		ArrayList<Integer> result = new ArrayList<>();
		
		// 탐색해서 큐에 담아야지 : ArrayDeque를 쓰자
		ArrayDeque<Integer> dq = new ArrayDeque<>();
		
		// 방문 내역을 전부 false로 초기화한다.
		Arrays.fill(visited, false);
		
		// 첫번째 방문할 곳을 큐에 넣는다.
		// 지금 역방향 탐색이므로 endCity부터 넣어야지
		dq.add(startCity);
		
		// 큐가 빌 때 까지 탐색
		while(!dq.isEmpty()) {
			// 큐에 있는 값 중 첫번째 값을 뺀다
			int now = dq.poll();
			
			// 만약 이미 방문했다면? 넘어가자
			if (visited[now]) {
				continue;
			}
			
			// 지금 방문한 곳은 방문 처리하고
			visited[now] = true;
			
			// 지금 큐에서 뽑은 정점의 인접한 노드들을 탐색한다
			for (Node next : adjList_rev[now]) {
				if(dist[now] == dist[next.dest] + next.cost) {
					dq.add(next.dest);
					
					// 중복 처리 중요... 한번 이미 담았으면 같은거 또 있는건 제껴
					break;
				}
			}
			
			// 시작점이면 따로 담을 필요 없음, 다음으로 넘어가기
			if(now == startCity) {
				count += 1;
				result.add(now);
				continue;
			}
			
			// 도착점이 아니면 전부 result 배열에 보관
			// 시작과 끝점이 아니면 일단 count를 다 올려줌
			if(now != endCity) {
				count += 1;
				result.add(now);
			}
			
			if(now == endCity) {
				count += 1;
				result.add(now);
			}
		}
		
		return result;
	}

	private static void dijkstra(int startCity, int endCity) {
		PriorityQueue<Node> pq = new PriorityQueue<>(new Comparator<Node>() {

			@Override
			public int compare(Node o1, Node o2) {
				return Integer.compare(o1.cost, o2.cost);
			}
		});
		
		Arrays.fill(dist, Integer.MAX_VALUE);
		dist[startCity] = 0;
		
		pq.add(new Node(startCity, 0));
		
		while(!pq.isEmpty()) {
			Node now = pq.poll();
			
			if (dist[now.dest] < now.cost) {
				continue;
			}
			
			for (Node next : adjList[now.dest]) {
				if(dist[next.dest] > now.cost + next.cost) {
					dist[next.dest] = now.cost + next.cost;
					pq.add(new Node(next.dest, dist[next.dest]));
				}
			}
		}		
	}

}

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

문제

문제

출처

ICPC

어떤 부분을 놓쳤을까요? ㅜㅜ (java)

hyunjunge 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말