다익스트라 알고리즘은 최단 경로 알고리즘 중에 가장 기초가 되는 알고리즘입니다. 🏃🏃 그동안 최단거리를 구할 때 죽어라고 BFS를 이용해왔으나(제일 재밌는걸요), 가중치가 있는 상황에서는 항상 풀이가 까다로웠습니다. 저는 이제까지 BFS의 다음 노드 탐색 과정에서 가중치가 더 적은 노드의 탐색을 단순히 '코드 상으로 더 위쪽에' 작성함으로서 먼저 탐색하도록 했습니다. 이는 나름 괜찮은 방법이였지만, 당연히 한계가 있었습니다. 이럴 때 사용 할 수 있는 것이 '최단 경로 알고리즘'입니다. 가중치가 더 적은 쪽을 우선적으로 탐색하도록 하는 알고리즘이죠. 1. 다익스트라 알고리즘: 가중치가 있는 그래프 탐색의 최단 경로 찾기. 셋 중에 가장 빠름! 2. 벨만-포드 알고리즘: 음수 가중치가 있는 그래프 탐색의 ..
https://www.acmicpc.net/problem/5719 5719번: 거의 최단 경로 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 장소의 수 N (2 ≤ N ≤ 500)과 도로의 수 M (1 ≤ M ≤ 104)가 주어진다. 장소는 0부터 N-1번까지 번호가 매겨져 있 www.acmicpc.net [백준 5719] 거의 최단 경로 (platinum 5) 거의 최단 경로 문제는 최단경로를 제외한 경로들 중 가장 짧은 경로를 찾아 그 길이를 출력하는 문제입니다. 최단 경로를 알아내는 과정이 여러번 필요할 것으로 예상되므로, 최단 경로 알고리즘 중 저에게 가장 익숙한 다익스트라 알고리즘으로 풀어보겠습니다. (저는 그래프 관련 알고리즘 중에 다익스트라가 제일 재미있는..
16933번: 벽 부수고 이동하기 3 (acmicpc.net) 16933번: 벽 부수고 이동하기 3 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000), K(1 ≤ K ≤ 10)이 주어진다. 다음 N개의 줄에 M개의 숫자로 맵이 주어진다. (1, 1)과 (N, M)은 항상 0이라고 가정하자. www.acmicpc.net [백준 16933] 벽 부수고 이동하기 3 (gold 1) 위 문제는 벽 부수고 이동하기 1, 2를 푼 이후에 풀어보는 것을 추천합니다. 벽뿌이 1, 2에서 새로운 요소가 추가된 문제들이기 때문입니다. 벽뿌이 3은 벽뿌이 1, 2에서 '가만히 있을 수 있는' 기능과, 낮과 밤의 개념이 추가되었습니다. 위 두가지 기능을 어떻게 구현하였는지를 중점으로 설명하겠습니다. 일..
