[BAEKJOON] 1753번 : 최단 경로 (JAVA)

2022. 2. 3. 23:30· Algorithm
반응형

- 알고리즘 분류 : 다이나믹 프로그래밍, Bottom-Up 방식

- 사용 언어 : JAVA

- 문제 요점

  1. 다익스트라 알고리즘을 이용하여 쉽게 풀이가 가능
  2. 다익스트라 알고리즘의 기초적인 문제

 

소스 설명은 주석을 참고해주세요.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

// 노드 클래스 선언
class Node implements Comparable<Node>{
	
	// 지점
	private int index;
	
	// 거리
	private int distance;
	
	// 생성자를 이용해 멤버변수 설정
	public Node(int index, int distance) {
		this.index = index;
		this.distance = distance;
	}
	
	public int getIndex() {
		return this.index;
	}
	
	public int getDistance() {
		return this.distance;
	}
	
	// 우선순위 큐에서 사용될 부분
	@Override
	public int compareTo(Node other) {
		// distance가 작은 것이 우선순위를 갖는다.
		if(other.distance > this.distance)
			return -1;
		else
			return 1;
	}
}

public class Main {

	// 무한으로 표현될 변수
	public static final int INF = (int)1e9;
	
	// 그래프 변수
	public static ArrayList<ArrayList<Node>> graph = new ArrayList<ArrayList<Node>>();
	
	// N : 정점의 갯수
	// M : 간선의 갯수
	// START : 시작점
	public static int N,M,START;
	
	// 시작점에서 각 노드별 최단 경로를 모아두는 배열
	public static int[] d;
	
	// 다익스트라 함수 (최단 경로 구하는 함수)
	public static void dijkstra() {
		
		// 우선순위 큐를 이용해 최단경로 구하기(시간 효율을 위함)
		PriorityQueue<Node> pq = new PriorityQueue<Node>();
		
		// 1. 무한으로 초기화
		Arrays.fill(d, INF);
		
		// 2. 시작점 우선순위 큐에 넣고 자기 자신은 0으로 갱신
		pq.offer(new Node(START, 0));
		d[START] = 0;
		
		// 3. 우선순위 큐가 빌 때까지 반복
		while(!pq.isEmpty()) {
			
			// 우선순위 큐에서 노드를 하나 꺼내고
			Node node = pq.poll();
			
			int now = node.getIndex();
			int distance = node.getDistance();
			
			// 최단거리에 기록된 것 보다 거리가 멀 경우, continue를 이용해 무시
			if(d[now] < distance) {
				continue;
			}
			
			// 반복
			for(int i=0; i<graph.get(now).size(); i++) {
				int cost = distance + graph.get(now).get(i).getDistance();
				
				// 현재까지의 거리 + i번까지의 거리가 최단거리에 기록된 것 보다 적을 때 갱신 및 우선순위 큐에 넣어줌
				if(d[graph.get(now).get(i).getIndex()] > cost) {
					d[graph.get(now).get(i).getIndex()] = cost;
					pq.offer(new Node(graph.get(now).get(i).getIndex(), cost));
				}
			}
		}
	}
	
	
	public static void main(String[] args) throws IOException{
		
		// 시간 절약을 위해 BufferedReader 이용
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		// 공백을 기준으로 문자열을 나눠주는 함수
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		START = Integer.parseInt(br.readLine());
		
		// 최단경로 기록용 변수 크기 선언
		d = new int[N+1];
		
		// 참고로 0. 첫번 째 리스트는 사용 X
		for(int i=0; i<=N; i++) {
			graph.add(new ArrayList<Node>());
		}
		
		// 간선의 갯수만큼 입력 반복
		for(int i=0; i<M; i++) {
			st = new StringTokenizer(br.readLine());
			
			int from = Integer.parseInt(st.nextToken());
			int to = Integer.parseInt(st.nextToken());
			int distance = Integer.parseInt(st.nextToken());
			
			graph.get(from).add(new Node(to,distance));
		}
		
		// 다익스트라 알고리즘을 이용해 최단경로 구하기
		dijkstra();
		
		// 결과 출력
		for(int i=1; i<=N; i++) {
			if(d[i] == INF) {
				System.out.println("INF");
			}
			else {
				System.out.println(d[i]);
			}
		}
	}
}
반응형

'Algorithm' 카테고리의 다른 글

[BAEKJOON] 13549번 : 숨바꼭질 3 (JAVA)  (0) 2022.02.07
[BAEKJOON] 1916번 : 최소 비용 구하기 (JAVA)  (0) 2022.02.04
[BAEKJOON] 1238번 : 파티 (JAVA)  (0) 2022.02.02
[BAEKJOON] 1389번 : 케빈 베이컨의 6단계 법칙 (JAVA)  (0) 2022.02.02
[이것이 코딩테스트다] 8. 최단 경로 - 실전 문제 풀이  (0) 2022.02.01
'Algorithm' 카테고리의 다른 글
  • [BAEKJOON] 13549번 : 숨바꼭질 3 (JAVA)
  • [BAEKJOON] 1916번 : 최소 비용 구하기 (JAVA)
  • [BAEKJOON] 1238번 : 파티 (JAVA)
  • [BAEKJOON] 1389번 : 케빈 베이컨의 6단계 법칙 (JAVA)
멍목
멍목
개발 관련 새롭게 알게 된 지식이나 좋은 정보들을 메모하는 공간입니다.
반응형
멍목
김멍목의 개발블로그
멍목
전체
오늘
어제
  • 분류 전체보기 (514)
    • BE (190)
      • Spring (21)
      • Java (141)
      • Kotlin (6)
      • JPA (22)
    • FE (33)
      • Javascript (16)
      • Typescript (0)
      • React (5)
      • Vue.js (9)
      • JSP & JSTL (3)
    • DB (32)
      • Oracle (22)
      • MongoDB (10)
    • Algorithm (195)
    • Linux (8)
    • Git (6)
    • etc (42)
    • ---------------------------.. (0)
    • 회계 (4)
      • 전산회계 2급 (4)
    • 잡동사니 (2)

블로그 메뉴

  • 홈
  • 관리

공지사항

인기 글

태그

  • 코틀린
  • Effective Java
  • 자기 개발
  • MongoDB 기초부터 실무까지
  • 이펙티브 자바
  • 자바공부
  • JPA
  • 이펙티브자바
  • 자기공부
  • 프로젝트로 배우는 Vue.js 3
  • Oracle
  • 자바 테스팅 프레임워크
  • junit5
  • 알고리즘 공부
  • 전산회계 2급 준비
  • JPA 공부
  • 자바 공부
  • MongoDB with Node.js
  • 자기 공부
  • java 8
  • 더 자바 Java 8
  • vue3 공부
  • 알고리즘공부
  • 코테공부
  • 자기개발
  • 코테 공부
  • 더 자바 애플리케이션을 테스트하는 다양한 방법
  • 자바 개발자를 위한 코틀린 입문
  • Java to Kotlin
  • MongoDB 공부

최근 댓글

최근 글

hELLO · Designed By 정상우.v4.2.0
멍목
[BAEKJOON] 1753번 : 최단 경로 (JAVA)
상단으로

티스토리툴바

개인정보

  • 티스토리 홈
  • 포럼
  • 로그인

단축키

내 블로그

내 블로그 - 관리자 홈 전환
Q
Q
새 글 쓰기
W
W

블로그 게시글

글 수정 (권한 있는 경우)
E
E
댓글 영역으로 이동
C
C

모든 영역

이 페이지의 URL 복사
S
S
맨 위로 이동
T
T
티스토리 홈 이동
H
H
단축키 안내
Shift + /
⇧ + /

* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.