메이쁘

(JAVA) 백준 5214번 : 환승 --- [BFS] 본문

Algorithm/Baekjoon

(JAVA) 백준 5214번 : 환승 --- [BFS]

메이쁘 2020. 10. 5. 23:29

www.acmicpc.net/problem/5214

 

5214번: 환승

첫째 줄에 역의 수 N과 한 하이퍼튜브가 서로 연결하는 역의 개수 K, 하이퍼튜브의 개수 M이 주어진다. (1 ≤ N ≤ 100,000, 1 ≤ K, M ≤ 1000) 다음 M개 줄에는 하이퍼튜브의 정보가 한 줄에 하나씩 주어

www.acmicpc.net

 

안녕하세요.

 

조금 꼬아놓은 BFS 알고리즘 문제 입니다.

 

 

 

처음에는 단순히 양방향 그래프로 생각하고 진행했다가 O(1000^3) 및 메모리 초과로 인해 실패했었습니다.

 

이후, 다른 풀이자분의 소스코드를 참고해서

역 / 큐브 두 부분으로 나눠 배열을 만들어 저장한 다음,

 

특정 역에서 꺼낼 때, 역이 포함되어있는 큐브를 순회합니다.

 

 

이 때, 꺼낸 큐브의 모든 역을 순회하며 다음 역으로 이동하는 BFS를 진행합니다.

 

즉, 역 -> 큐브 -> 역 으로 역 -> 역 의 과정을 거치는 것과 똑같다고 생각하면 됩니다.

이후에는 똑같이 다익스트라 알고리즘을 활용해서 최소 역의 개수를 배열에 담아가며 N 지점까지 BFS 반복합니다.

 

 

이렇게 해서 얼추 정답은 나왔지만, 메모리 및 소요 시간이 기하급수적으로 높더라구요...

 

 

맞은 사람에서 1등 갓(IKSU) 님의 코드를 보고, 이건 예술이다 느꼈고, 이를 설명하는 포스팅을 해야겠다 마음먹었습니다.

*** 정말 감사합니다.

 

 

 

어떻게 풀었냐?

 

  1)  굳이 두 배열을 만들 필요가 없이 하나의 배열을 활용하면 됩니다. 즉, n + m + 1 길이의 ArrayList<Integer> 를 만들면 됩니다! 이는 곧 그래프가 됩니다. 1 ~ N 까지는 역 번호가, N+1 ~ M 까지는 큐브의 번호가 들어갑니다.

  

  2)  다익스트라 배열 또한 n + m + 1 길이의 int 배열을 만들어 활용합니다. 역 -> 큐브 -> 역 의 과정은 같지만, 역 -> 큐브 일 때에는 큐브의 dijkstra 원소값은 이전 역의 dijkstra 원소값과 같고, 큐브 -> 역 일 때에는 이전 큐브의 dijkstra 원소 값 + 1 과 같습니다.

  *** 이해가 잘 안되면 소스코드를 보시면 될 것 같아요!

 

  3)  처음 해당 지점에 도달했을 때가 가장 최소 역의 개수 입니다. 그렇기 때문에, Queue를 사용해도 되고, 기존에 도달했던 경우가 있다면 가볍게 무시해도 됩니다.

 

 

 

이 매커니즘을 활용한다면, 쉽게 푸실 수 있을겁니다!

 

자세한 사항은 하단 소스코드를 참고해주세요!

 

댓글 부탁드립니다.

 

 

감사합니다!

*** author : github.com/ISKU/Algorithm

 

 

 

 

 

 

소스코드


 

Comments