[BAEKJOON] 1719번 : 택배 스페셜 저지 (JAVA)

2022. 10. 18. 23:11· Algorithm
반응형

- 알고리즘 분류 : 다익스트라

- 사용 언어 : JAVA

- 문제 요점

    - 한 구역씩 다익스트라 알고리즘을 확인

    - 다익스트라 알고리즘에서 최단 거리를 출력하는 게 아닌, 최단 거리 루트 중 첫 번째로 방문하는 지역의 번호를 추출해야함( 첫번 째 방문 지역을 추출하는 방법은 소스 주석 참고)

    - 다익스트라 설명 및 예제 : https://ajdahrdl.tistory.com/120

 

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

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

public class Main {

	static class Node{
		int pos;
		int dis;
		
		public Node(int pos, int dis) {
			this.pos = pos;
			this.dis = dis;
		}
	}
	
	static ArrayList<ArrayList<Node>> map = new ArrayList<>();
	
	static int N, M;
	static int[][] d;
	static int[][] firstArr;
	static final int INF = Integer.MAX_VALUE;
	
	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		
		d = new int[N+1][N+1];
		firstArr = new int[N+1][N+1];
		
		for(int i=0; i<=N; i++) {
			map.add(new ArrayList<Node>());
		}
		
		for(int i=0; i<M; i++) {
			st = new StringTokenizer(br.readLine());
			
			int posA = Integer.parseInt(st.nextToken());
			int posB = Integer.parseInt(st.nextToken());
			int dis = Integer.parseInt(st.nextToken());
			
			// 양방향 이동 가능
			map.get(posA).add(new Node(posB, dis));
			map.get(posB).add(new Node(posA, dis));
		}
		
		// 한 군데씩 다익스트라 확인
		for(int i=1; i<=N; i++) {
			dijkstra(i);
		}
		
		StringBuilder sb = new StringBuilder();
		
		for(int i=1; i<=N; i++) {
			for(int j=1; j<=N; j++) {
				if(i == j) {
					sb.append("- ");
				}
				else {
					sb.append(firstArr[i][j]+ " ");
				}
			}
			sb.append("\n");
		}
		
		System.out.println(sb.toString());
	}
	
	static void dijkstra(int START) {
		Queue<Node> q = new LinkedList<>();
		q.offer(new Node(START, 0));
		
		Arrays.fill(d[START], INF);
		d[START][START] = 0;
		
		
		while(!q.isEmpty()) {
			Node node = q.poll();
			
			if(d[START][node.pos] < node.dis) {
				continue;
			}
			
			for(int i=0; i<map.get(node.pos).size(); i++) {
				Node next = map.get(node.pos).get(i);
				
				if(d[START][next.pos] > (d[START][node.pos] + next.dis)) {
					d[START][next.pos] = d[START][node.pos] + next.dis;
					q.offer(new Node(next.pos, d[START][node.pos] + next.dis));
					
					// A에서 B까지 가는 최단 루트 = B에서 A까지의 최단 루트
					// 즉, 첫 번째로 거치는 구역을 구하려면 아래와 같이 하면 된다.
					// 예를 들어, 1번에서 4번까지 1-2-3-4 루트로 갔다면. 4번에서 1번까지의 최단루트도 4-3-2-1이다.
					// 그러니까, 1번에서 4번까지 가는 최단 루트를 구했을 때, 반대로 4번에서 1번으로 가는 최단 루트 중 첫 번째로 들리는 구역이 아래라는 뜻.
					firstArr[next.pos][START] = node.pos;	
				}
			}
		
		}
	}

}
반응형

'Algorithm' 카테고리의 다른 글

[BAEKJOON] 1987번 : 알파벳 (JAVA)  (0) 2022.10.23
[BAEKJOON] 11724번 : 연결 요소의 개수 (JAVA)  (0) 2022.10.22
[BAEKJOON] 6087번 : 레이저통신 다국어 (JAVA)  (0) 2022.10.18
[BAEKJOON] 14938번 : 서강그라운드 (JAVA)  (0) 2022.10.18
[Programmers] 등산코스 정하기 (JAVA)  (0) 2022.10.10
'Algorithm' 카테고리의 다른 글
  • [BAEKJOON] 1987번 : 알파벳 (JAVA)
  • [BAEKJOON] 11724번 : 연결 요소의 개수 (JAVA)
  • [BAEKJOON] 6087번 : 레이저통신 다국어 (JAVA)
  • [BAEKJOON] 14938번 : 서강그라운드 (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)

블로그 메뉴

  • 홈
  • 관리

공지사항

인기 글

태그

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

최근 댓글

최근 글

hELLO · Designed By 정상우.v4.2.0
멍목
[BAEKJOON] 1719번 : 택배 스페셜 저지 (JAVA)
상단으로

티스토리툴바

개인정보

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

단축키

내 블로그

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

블로그 게시글

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

모든 영역

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

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