- Today
- Yesterday
- Total
메이쁘
(JAVA) 백준 5214번 : 환승 --- [BFS] 본문
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
소스코드
'Algorithm > Baekjoon' 카테고리의 다른 글
| (JAVA) 백준 5670번 : 휴대폰 자판 --- [트라이] (0) | 2020.10.09 |
|---|---|
| (JAVA) 백준 15559번 : 내 선물을 받아줘 --- [DFS] (2) | 2020.10.06 |
| (JAVA) 백준 16681번 : 등산 --- [다익스트라] (0) | 2020.10.04 |
| (JAVA) 백준 16934번 : 게임 닉네임 --- [트라이] (0) | 2020.10.04 |
| (JAVA) 백준 15284번 : 너 봄에는 캡사이신이 맛있겠다 --- [수학, 조합, 정렬] (0) | 2020.10.03 |