본문 바로가기

다익스트라4

[Python] 프로그래머스 배달 https://school.programmers.co.kr/learn/courses/30/lessons/12978 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr풀이양방향 그래프에서 1번노드를 시작으로, 모든 연결 노드까지의 최단 거리를 구한 후 K 이하의 노드 갯수를 세면 되는 문제입니다. 다익스트라 알고리즘을 사용해 문제를 해결할 수 있습니다. 1. 양방향 그래프 만들기2. 다익스트라 알고리즘  다익스트라 알고리즘은 우선순위 큐를 사용해 구현할 수 있습니다.1. 모든 노드를 최대 거리(INF)로 초기화 합니다.2. heapq에 (키, 값) 형태로 넣어줍니다.. 2024. 9. 27.
[C++] 프로그래머스 합승 택시 요금 - 플로이드 와샬/다익스트라 https://school.programmers.co.kr/learn/courses/30/lessons/72413 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 시작 지점s와 도착 지점 a, b 를 연결하는 최소 비용 경로를 찾는 문제이다. 각 정점 s, a, b(다익스트라) 또는 모든 노드(플로이드 와샬)에서 모든 노드로의 최단 거리를 구한 후, 임의의 노드를 선택해서, 해당 노드에서 s, a, b와 연결되는 최소 비용을 구하면 된다. 이렇게 하면 s-s, s-a, s-b 와 같이 합승을 하지 않는 경우 또한 검사할 수 있다. 구현은 플로이드 와샬.. 2023. 2. 14.
[Algorithm] 다익스트라(Dijkstra) 1. 다이나믹 프로그래밍을 활용한 대표적인 최단경로 탐색 알고리즘 2. 가중치 그래프에서, 임의의 점에서 목표점까지의 최소 비용 거리를 탐색할 수 있다. 3. 현재 점과 연결된 노드 중, 가중치가 가장 작은 노드를 선택 방문하여, 시작점으로부터 그 점까지의 거리를 업데이트 한다. 4. 3번 과정을 반복하면서, 특정 노드를 직접 방문했을 때 보다, 다른 점을 거쳐서 왔을 때의 거리가 작다면, 그 거리를 업데이트 하게 된다. 우선순위 큐 사용 알고리즘 1. 가중치 그래프를 저장하기 위한 구조체와 우선순위 큐(최소 힙)를 선언한다. 벡터를 사용해 구현할 시, 최소 가중치 노드를 찾기 위한 for loop 가 필요한데, 최소힙을 사용하면 이 과정을 O(log N)으로 줄일 수 있다. 2. 우선순위 큐에 시작점을.. 2023. 1. 21.
[C++] 백준 1753 최단경로 [Gold4] 문제 방향그래프가 주어지면 주어진 시작점에서 다른 모든 정점으로의 최단 경로를 구하는 프로그램을 작성하시오. 단, 모든 간선의 가중치는 10 이하의 자연수이다. 풀이 시작점에서 다른 모든 정점으로의 최단 경로는 다익스트라 알고리즘으로 구할 수 있다. BFS 와 비슷하며 알고리즘 개념은 다음과 같다. 다익스트라 알고리즘 1. 현재 노드와 연결된 노드를 찾으면서 누적 거리 값을 계산한다. 2. 연결된 노드가 가지고 있는 거리 값이 현재 누적된 거리값 보다 크다면, 현재 누적된 거리가 최단 경로 이므로 업데이트 한다. ( 기본적으로, 모든 노드는 무한대 값으로 거리 값이 초기화 되어있다.) 3. 다음으로, 현재 알고 있는 누적 거리 중 가장 최소인 정점을 선택해서 뻗어나간다. 4. 3번 과정에서 현재 누적 거.. 2023. 1. 20.

티스토리툴바