알고스팟 문제 링크: https://algospot.com/judge/problem/read/FIRETRUCKS
algospot.com :: FIRETRUCKS
소방차 문제 정보 문제 한겨울 날씨가 추워지면 각종 난방 기구 때문에 화재가 발생하기 쉽습니다. 어느 추운 겨울날 서울 시내 n개의 지역에 동시에 화재가 발생했습니다. 피해를 최소화하기
algospot.com
여러개의 지역들이 그래프 형태로 입력으로 주어지고 그중 불난곳과 소방서가 있는곳을 지정해준다.
이때 불난곳과 가장가까운 소방서에서 소방차가 출발한다 했을때 불난곳 각각에 대해 소방차가 도착할 때까지 걸리는 시간의 합을 구하는 문제이다.
다익스트라를 이용하면 문제를 쉽게 풀 수 있겠다고 생각할 수 있다.
하지만 불난곳 각각에 대해 모두 다익스트라를 실행하기엔 제한된 시간안에 계산를 완료하기 불가능하다.
다른 방법으로 가상의 지역으로하는 정점을 하나 만들고 해당 정점에서 소방서까지의 거리를 0으로 하는 간선을 연결시킨다.
이제 가상의 정점에서 출발하는 다익스트라를 이용하면 한번의 다익스트라 계산으로 각 소방서에서 각각의 불난곳까지의 최소거리들을 알 수 있게된다.
코드 원본: https://github.com/sbl133/JongmanBook/blob/main/30.%20ShortestPath/FIRETRUCKS.cpp
GitHub - sbl133/JongmanBook
Contribute to sbl133/JongmanBook development by creating an account on GitHub.
github.com
댓글을 통한 코드리뷰, 질문, 지적 언제든 환영입니다!
reference: 프로그래밍 대회에서 배우는 알고리즘 문제해결전략2
'Algorithm > algospot' 카테고리의 다른 글
| algospot 시간여행(문제 ID: TIMETRIP) c++ (0) | 2022.03.31 |
|---|---|
| algospot 철인 n종 경기 (문제 ID: NTHLON) c++ (0) | 2022.03.14 |
| algospot 회의실 배정(문제 ID: MEETINGROOM) c++ (0) | 2022.03.05 |
| algospot 감시 카메라 설치(문제 ID: GALLERY) c++ (0) | 2022.03.03 |
| algospot 보안종결자(문제 ID: NH) c++ (0) | 2022.03.01 |