Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |
Tags
- Effective Java
- 플로이드-와샬
- 동적계획법
- 백준
- JUnit 5
- 투 포인터
- 유니온 파인드
- BFS
- 위상정렬
- 프로그래머스
- 완전탐색
- 문자열
- dfs
- 구현
- mst
- 알고리즘
- 시뮬레이션
- Network
- 이분탐색
- 스택
- 백트래킹
- swea
- 세그먼트 트리
- 에라토스테네스의 체
- CS
- 그리디
- 수학
- 후니의 쉽게 쓴 시스코 네트워킹
- java
- Kotlin
Archives
목록위상 정렬 (1)
반갑습니다!
[백준] 1948 임계 도로
1948번: 임계경로 boj.kr 풀이 이 문제는 위상 정렬과 BFS를 사용해서 해결했다. 우선 위상 정렬을 사용하면 도착 도시까지 걸리는 최대 시간을 쉽게 구할 수 있다. 그리고 나면 관건은 1분도 쉬지 않고 달려야 하는 도로를 세는 것이다. 이는 위상 정렬을 했던 결과를 이용해서 구할 수 있다. 위상 정렬을 수행해서 각 도시까지 도착하는데 걸리는 최대 시간을 알아냈기 때문에 이번에는 도착지에서 출발지로 역행하면서 탐색해준다. 어떻게 도로의 개수를 찾을 수 있는지는 그림을 보면서 이해하자. 위의 그림처럼 1번 도시까지의 최대 시간이 7, 2번 도시까지의 최대 시간이 17이고 1번 도시와 2번 도시 사이의 도로를 건너는데는 10분이 걸린다고 가정하자. 그렇다면 2번 도시에서 1번 도시로 탐색을 할 때 2..
알고리즘 문제 풀이
2020. 10. 8. 17:09