(JAVA) 백준 2211번 : 네트워크 복구

https://www.acmicpc.net/problem/2211

2211번: 네트워크 복구

 

다익스트라 문제이다.

 

 

처음에 

1을 제외한 나머지를 다익스트라 알고리즘 돌렸더니 시간 초과가 발생했었다...

 

문제를 잘못 이해해서..ㅠㅠㅠ

 

1에서 출발해서 2 ~ n에 도착하는 최단 경로들을 구하면 되는 것인데,

2 ~ n 에서 1까지의 최단 경로를 다익스트라 알고리즘 한 번씩 실행해가며 구하려는 내 착오...

 

 

매커니즘

---

매커니즘은 크게 차이가 없다.

 

문제를 보면

 

 

1) 1번의 뜻 = 최소 개수 = 최단 경로

2) 2번의 뜻 = 최단 거리를 구하라는 뜻

 -> 다익스트라 알고리즘을 사용해서 최단 경로를 구하라는 문제.

 

또, 완전쌍방향 방식이기 때문에 양방향 그래프이며,

출력 시 임의의 순서이기 때문에 시작과 출발 Vertex가 달라도 된다.

 

 

 

 

다른 다익스트라 알고리즘과 동일하게 

 

1) 입력 값에서 (시작 - 끝) + Weight 를 입력받아 그래프를 만든다.

*** 양방향이기 때문에, (시작 - 끝) 과 (끝 - 시작) 두 개의 간선을 포함해야 한다.

 

2) 시작 지점을 1로 하는 다익스트라 알고리즘을 실행한다.

 

여기서부터 다른데,

 

3) 다익스트라 알고리즘을 진행하면서 최단 거리의 경로까지 파악해야 한다.

 

 

int 배열을 하나 만들고,

최단 경로를 발견해서 우선순위 큐에 새로운 시작점을 담은 다음

배열[end] = start 가 되도록 값을 설정한다.

 

 

예를 들어,

1 -> 2 가 최단 거리라고 했을 때,

배열[2] = 1 로 설정하라는 뜻이다.

*** 잘 이해가 가지 않으면 소스코드를 참고하세욥

  

 

4) 모든 최단 거리를 찾은 다음, 1번 컴퓨터를 제외한 나머지 컴퓨터를 for문으로 순차적으로 탐색하며

각 컴퓨터에서 1번 컴퓨터까지의 최단 경로를 3)에서 설정한 배열을 가지고 역순으로 거슬러 올라가면서 찾는다. (while문을 통해서)

 

또 예를 들어,

1 -> 2 -> 4 가 있다면

 

배열[4] = 2

배열[2] = 1

배열[1] = 0

0이면 4번 컴퓨터의 경로 탐색 종료.

 

 

이런 방식으로 2 ~ N번 컴퓨터를 하나씩 경로 탐색한 후

각 간선들의 (시작 - 끝) 값을 HashSet<String>에 담는다.

*** HashSet에 담는 이유는 중복된 간선이 존재할 수 있는데, HashSet의 특성인 중복 불가능 을 살려 간선 값의 중복을 방지하기 때문이다.

 

5) HashSet 데이터 출력!

 

 

 

감사합니다.

 

소스코드

---