티스토리 뷰
codeground : 캠퍼스와 도로(1) [SCPC 2015 - 1차 예선]
https://www.codeground.org/practice/practiceProbView.do?probId=15
SW역량테스트를 맞아 codeground문제들도 써보려고 한다.
그 첫번째 문제..
이 문제는 v번의 다익스트라 알고리즘으로 떠오르는 아이디어 그대로 해결할 수있다.
시간복잡도는 v*(v+e)log(v+e)가 되어 시간안에 충분히 해결할 수 있을 듯 하다.
다만, 방문하는 도시까지의 거리가 같을 때가 문제 ㅜㅜ...
힙에 push하기 전에 방문노드를 체크해주면 왜안되는지 모르겠다. 아직 밝혀내지 못했음...
해결한 방법은, 코드가 조금 길어지긴하지만 스타팅 지점인 v번째 도시에 대해 다익스트라 알고리즘으로 모든 경로까지의 최단거리를 구한 후, 각 edge가 v번째 도시의 최단경로를 만드는 데 참여하는지 확인하는 방법으로 해결하였다.
'Problem Solving' 카테고리의 다른 글
codeground : 프리랜서 [SCPC 2016 - 2차 예선] (0) | 2016.10.12 |
---|---|
codeground : 대피소 [SCPC 2016 - 1차 예선] (0) | 2016.10.01 |
boj 2381 : 최대거리 (0) | 2016.09.22 |
boj 1238 : 파티 (0) | 2016.09.22 |
boj 11060 : 점프점프 (0) | 2016.09.22 |
공지사항
최근에 올라온 글
최근에 달린 댓글
- Total
- Today
- Yesterday
링크
TAG
- 백준
- 백준 1647
- 문제 풀이
- scpc
- boj 용액
- dp
- 백준알고리즘
- 백준 용액
- 알고리즘
- 백준 1799
- boj 앱
- 백준 1806
- BOJ
- 백준 부분합
- 네블컵 2회
- 백준 7579 앱
- boj 1806
- 백준 앱
- 연습문제
- boj 1799
- 백준 도시 분할 계획
- 2469
- boj 7579
- 풀이
- codeground
- 백준 비숍
- 10159
- 백준 2467 용액
- SCPC 2016
- 도시 분할 계획
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | ||||||
2 | 3 | 4 | 5 | 6 | 7 | 8 |
9 | 10 | 11 | 12 | 13 | 14 | 15 |
16 | 17 | 18 | 19 | 20 | 21 | 22 |
23 | 24 | 25 | 26 | 27 | 28 | 29 |
30 | 31 |
글 보관함