[BAEKJOON] 2211번 : 네트워크 복구 (JAVA)

2023. 3. 12. 23:49· Algorithm
반응형

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

- 사용 언어 : JAVA

- 문제 요점

    - 기존 다익스트라 알고리즘을 사용하면서, 경로를 저장

 

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


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;

public class Baekjoon_No_2211 {
    static class Network implements Comparable<Network>{
        int idx;
        int time;

        ArrayList<Integer> path = new ArrayList<>();

        public Network(int idx, int time) {
            this.idx = idx;
            this.time = time;
            path.add(idx);
        }

        @Override
        public int compareTo(Network o) {
            return o.time - this.time;
        }
    }

    public static void main(String[] args) throws IOException {
        final int INF = 20_000_000;

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        ArrayList<ArrayList<Network>> map = new ArrayList<>();
        int N = Integer.parseInt(st.nextToken());       // 컴퓨터 갯수
        int M = Integer.parseInt(st.nextToken());       // 회선의 갯수

        for(int i=0; i<=N; i++){
            map.add(new ArrayList<>());
        }

        PriorityQueue<Network> pq = new PriorityQueue<>();

        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 time = Integer.parseInt(st.nextToken());

            // 양방향
            map.get(posA).add(new Network(posB, time));
            map.get(posB).add(new Network(posA, time));
        }

        // 1. 각 컴퓨터마다 최단 경로 구하기
        int[] d = new int[N+1];
        ArrayList<Integer>[] minPathArr = new ArrayList[N+1];

        Arrays.fill(d, INF);

        int START = 1;      // 슈퍼컴퓨터는 1로 고정
        d[START] = 0;

        pq.offer(new Network(START, 0));
        while(!pq.isEmpty()){
            Network now = pq.poll();

            int idx = now.idx;      // 현재 노드
            int time = now.time;    // 현재 노드까지의 시간 합계

            if(d[idx] < time){
                continue;
            }

            for(Network next : map.get(idx)){
                int totalTime = time + next.time;

                if(totalTime < d[next.idx]){
                    d[next.idx] = totalTime;
                    pq.offer(new Network(next.idx, totalTime));

                    ArrayList<Integer> minPath = new ArrayList<>();
                    for(int num : now.path)
                        minPath.add(num);
                    minPath.add(next.idx);

                    minPathArr[next.idx] = minPath;
                }
            }
        }

        // 2. 각 컴퓨터에 대한 최단 경로를 바탕으로 사용된 경로 표시
        boolean[][] resultArr = new boolean[N+1][N+1];
        int resultCnt = 0;
        for(int i=2; i<=N; i++){
            for(int j=0; j < minPathArr[i].size()- 1; j++){
                int from = minPathArr[i].get(j);
                int to = minPathArr[i].get(j+1);

                if(to < from){
                    int temp = to;
                    to = from;
                    from = temp;
                }

                if(resultArr[from][to] == false){
                    resultCnt++;
                    resultArr[from][to] = true;
                }
            }
        }

        // 3. 결과 출력
        System.out.println(resultCnt);
        for(int i=1; i<=N; i++){
            for(int j=1; j<=N; j++){
                if(resultArr[i][j]){
                    System.out.println(i + " " + j);
                }
            }
        }
    }
}
반응형

'Algorithm' 카테고리의 다른 글

[BAEKJOON] 3184번 : 양 (JAVA)  (0) 2023.03.22
[BAEKJOON] 2251번 : 물통 (JAVA)  (0) 2023.03.21
[BAEKJOON] 1461번 : 도서관 (JAVA)  (0) 2023.02.25
[BAEKJOON] 1041번 : 주사위 (JAVA)  (0) 2023.02.19
[BAEKJOON] 12904번 : A와 B (JAVA)  (0) 2023.02.12
'Algorithm' 카테고리의 다른 글
  • [BAEKJOON] 3184번 : 양 (JAVA)
  • [BAEKJOON] 2251번 : 물통 (JAVA)
  • [BAEKJOON] 1461번 : 도서관 (JAVA)
  • [BAEKJOON] 1041번 : 주사위 (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)

블로그 메뉴

  • 홈
  • 관리

공지사항

인기 글

태그

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

최근 댓글

최근 글

hELLO · Designed By 정상우.v4.2.0
멍목
[BAEKJOON] 2211번 : 네트워크 복구 (JAVA)
상단으로

티스토리툴바

개인정보

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

단축키

내 블로그

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

블로그 게시글

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

모든 영역

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

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