광규니
광규니네
광규니
전체 방문자
오늘
어제
  • 분류 전체보기 (154)
    • 알고리즘 (100)
      • 알고리즘 개념 (2)
      • 문제 풀이 (96)
    • 주절주절 (19)
      • 자격증, 활동 후기 (4)
      • 전시회 후기 (3)
      • 이모저모 (2)
      • 회고 (3)
      • 뜨럼 (7)
    • 운영체제 (9)
    • 개발 지식 (9)
      • Apple Watch (4)
      • MySQL (2)
      • Eclipse (1)
      • XCode (1)
    • 네트워크 공부 (1)
    • 데이터베이스 공부 (5)
    • Java 공부 (7)
    • TMP (1)

블로그 메뉴

  • 홈
  • 태그
  • 방명록

공지사항

인기 글

태그

  • 합주
  • 알고리즘
  • 오블완
  • 백준
  • BOJ
  • 컴퓨터 사이언스
  • 애플워치 앱 만들기
  • 애플워치 앱
  • 다이나믹 프로그래밍
  • 개념
  • 파이썬
  • 프로그래머스
  • DP
  • 드린이
  • 자바
  • 티스토리챌린지
  • BFS
  • 운영체제
  • OS
  • 구현

최근 댓글

최근 글

티스토리

250x250
hELLO · Designed By 정상우.
광규니

광규니네

카테고리 없음

[Java/자바 백준 11779] 최소비용 구하기2

2022. 3. 31. 18:47
반응형

풀이

이 문제 정말 매콤했다...

 

일단은 문제 자체에서 주의해야할게

테스트케이스에서 다른 답도 답이 될 수 있다.

스페셜저지로 나온 문제기 때문에 다른 답도 나올 수 있으며,

테케 자체에서도 답이 1,3,5 이지만

1,4,5 도 똑같이 답이 된다... 

이점을 유의하자.. 이거때문에 시간을 많이 썼다.

 

또 시간 초과 나서 route 배열에 전 idx를 담는 로직으로 바꾸다가,

start idx를 특별한 값(여기선-1)로 초기 안해줘서

시간 음청 썼다 ~

-> int배열이 디폴트가 0이기때문에 출발지라는 걸 인식하기위해 -1로 초기화

 

 

풀이를 시작하면

우선 다익스트라를 사용하는 문제이지만, 경로까지 알아야하므로 한 번 더 생각해줘야한다.

고로 route배열을 만들어서 다익스트라 중 최솟값이 될 때 그 전 도시 인덱스를 담아주었따.

 

그 뒤 end -> start로 다시 찾아갈때, route를 써서 routes에 넣어주었다.

시간을 좀 더 줄이고자 stringbuilder를 사용햇다.

 

끝

import java.io.*;
import java.util.*;

public class Main {
	static int N, V, E, start, end;
	static int[] distance;
	static boolean[] visited;
	static int[] route;
	static ArrayList<Node>[] adjList;
	static ArrayList<Integer> routes;
	static StringBuilder sb = new StringBuilder();
	static final int INF = Integer.MAX_VALUE;
	
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		V = Integer.parseInt(br.readLine());
		E = Integer.parseInt(br.readLine());
		adjList = new ArrayList[V];
		distance = new int[V];
		visited = new boolean[V];
		route = new int[V];
		
		Arrays.fill(distance, INF);
		Arrays.fill(route, -1);
		for(int i = 0 ; i < V ;i++) {
			adjList[i] = new ArrayList<Node>();
		}
		
		for(int i = 0 ; i < E ; i++) {
			st = new StringTokenizer(br.readLine());
			int u = Integer.parseInt(st.nextToken()) - 1;
			int v = Integer.parseInt(st.nextToken()) - 1;
			int w = Integer.parseInt(st.nextToken());
			adjList[u].add(new Node(v, w));
		}
		st = new StringTokenizer(br.readLine());
		start = Integer.parseInt(st.nextToken()) - 1;
		end = Integer.parseInt(st.nextToken()) - 1;
		
		distance[start] = 0;
		route[start] = -1;
		for(int i = 0 ; i < V ; i++) {
			int min = Integer.MAX_VALUE;
			int minVertex = -1;
			for(int j = 0 ; j < V ; j++) {
				if(!visited[j] && distance[j] < min) {
					min = distance[j];
					minVertex = j;
				}
			}
			
			if(minVertex == -1) break;
			visited[minVertex] = true;
			for(Node next : adjList[minVertex]) {
				if(!visited[next.v] && distance[next.v] > min + next.w) {
					
					distance[next.v] = min + next.w;
					route[next.v] = minVertex;
				}
			}
		}
		sb.append(distance[end]).append("\n");
		visited = new boolean[V];
		visited[start] = true;
		routes = new ArrayList<>();
		int now = end;
		while(now != -1) {
			routes.add(now);
			now = route[now];
		}
		sb.append(routes.size()).append("\n");
		
		for(int i = routes.size() - 1 ; i >= 0 ; i--) {
			sb.append(routes.get(i) + 1).append(" ");
		}
		System.out.println(sb);
	}

	private static class Node {
		int v, w;
		public Node(int v, int w) {
			this.v = v;
			this.w = w;
		}
	}
}
반응형
저작자표시 (새창열림)
    광규니
    광규니
    공부 및 일상 올리기~

    티스토리툴바