BOJ13911 집구하기

BOJ 13911 집구하기

문제 원본

문제 설명

집을 구하려고 하는데 맥도날드와 스타벅스 까지 거리의 합이 최소인 거리를 구하는 문제

문제 풀이

1 Step

모든 맥도날드 위치에서 각 정점 까지 최단 거리(dijkstra)를 구한다.

2 Step

모든 스타벅스 위치에서 각 정점 까지 최단 거리((dijkstra)를 구한다.

3 Step

1번과 2번에서 구한 값을 이용해 맥도날드와 스타벅스 까지 거리합이 최소인 값을 구한다.

해설

우선순위 큐를 이용한 dijkstra는

의 시간복잡도를 가진다 E는 간선 개수 V는 정점 개수

따라서 이 문제의 해법은 dijkstra의 시간복잡도와 일치한다.

소스코드

소스코드는 GO언어와 C++코드 둘을 첨부합니다.

GO언어의 input 받는 부분을 관심있게 보시면 GO언어로 문제풀이 하는데 도움이 될것같습니다.

GO언어

C++코드

GO언어와 C++의 성능 비교

사용 알고리즘	GO	C++
우선순위큐 + 동적 배열	26868kb/256ms (input에서 string으로 받음)	10916kb/160ms