본문 바로가기

다익스트라

[BOJ] 백준 5719번 거의 최단 경로 (Java)
Dot Algo∙ DS/PS 2021. 12. 6. [BOJ] 백준 5719번 거의 최단 경로 (Java) #5719 거의 최단 경로 난이도 : 플레 5 유형 : 그래프 탐색 / 다익스트라 5719번: 거의 최단 경로 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 장소의 수 N (2 ≤ N ≤ 500)과 도로의 수 M (1 ≤ M ≤ 104)가 주어진다. 장소는 0부터 N-1번까지 번호가 매겨져 있 www.acmicpc.net ▸ 문제 요즘 많은 자동차에서는 GPS 네비게이션 장비가 설치되어 있다. 네비게이션은 사용자가 입력한 출발점과 도착점 사이의 최단 경로를 검색해 준다. 하지만, 교통 상황을 고려하지 않고 최단 경로를 검색하는 경우에는 극심한 교통 정체를 경험할 수 있다. 상근이는 오직 자기 자신만 사용 가능한 네비게이션을 만들고 있다. 이 네비게이션은 절대로 최단 경..
[BOJ] 백준 4485번 녹색 옷 입은 애가 젤다지? (Java)
Dot Algo∙ DS/PS 2021. 8. 23. [BOJ] 백준 4485번 녹색 옷 입은 애가 젤다지? (Java) #4485 녹색 옷 입은 애가 젤다지? 난이도 : 골드 4 유형 : 그래프 / 다익스트라 4485번: 녹색 옷 입은 애가 젤다지? 젤다의 전설 게임에서 화폐의 단위는 루피(rupee)다. 그런데 간혹 '도둑루피'라 불리는 검정색 루피도 존재하는데, 이걸 획득하면 오히려 소지한 루피가 감소하게 된다! 젤다의 전설 시리즈의 주 www.acmicpc.net ▸ 문제 젤다의 전설 게임에서 화폐의 단위는 루피(rupee)다. 그런데 간혹 '도둑루피'라 불리는 검정색 루피도 존재하는데, 이걸 획득하면 오히려 소지한 루피가 감소하게 된다! 젤다의 전설 시리즈의 주인공, 링크는 지금 도둑루피만 가득한 N x N 크기의 동굴의 제일 왼쪽 위에 있다. [0][0]번 칸이기도 하다. 왜 이런 곳에 들어왔냐고 묻는다면 밖에서..
[프로그래머스] 2021 카카오 인턴 #4 미로 탈출 (Java)
Dot Algo∙ DS/PS 2021. 7. 21. [프로그래머스] 2021 카카오 인턴 #4 미로 탈출 (Java) #4 미로 탈출 난이도 : LEVEL 4 유형 : 다익스트라 / 비트마스크 코딩테스트 연습 - 미로 탈출 4 1 4 [[1, 2, 1], [3, 2, 1], [2, 4, 1]] [2, 3] 4 programmers.co.kr 문제 신규 게임 ‘카카오 미로 탈출’이 출시되어, 라이언이 베타테스터로 참가했습니다. 위 예시 그림은 카카오 미로 탈출의 초기 상태를 나타냅니다. 1번부터 3번까지 번호가 붙어있는 3개의 방이 있고, 방과 방 사이를 연결하는 길에는 이동하는데 걸리는 시간이 표시되어 있습니다. 길은 화살표가 가리키는 방향으로만 이동할 수 있습니다. 미로에는 함정이 존재하며, 함정으로 이동하면, 이동한 함정과 연결된 모든 화살표의 방향이 바뀝니다. 출발지점인 1번 방에서 탈출이 가능한 3번 방까지 이동..
[BOJ] 백준 1854번 K번째 최단경로 찾기 (Java)
Dot Algo∙ DS/PS 2021. 7. 16. [BOJ] 백준 1854번 K번째 최단경로 찾기 (Java) #1854 K번째 최단경로 찾기 난이도 : 플레 5 유형 : 그래프 / 다익스트라 1854번: K번째 최단경로 찾기 첫째 줄에 n, m, k가 주어진다. (1 ≤ n ≤ 1000, 0 ≤ m ≤ 2000000, 1 ≤ k ≤ 100) n과 m은 각각 김 조교가 여행을 고려하고 있는 도시들의 개수와, 도시 간에 존재하는 도로의 수이다. 이어지는 m개의 줄에 www.acmicpc.net ▸ 문제 봄캠프를 마친 김진영 조교는 여러 도시를 돌며 여행을 다닐 계획이다. 그런데 김 조교는, '느림의 미학'을 중요시하는 사람이라 항상 최단경로로만 이동하는 것은 별로 좋아하지 않는다. 하지만 너무 시간이 오래 걸리는 경로도 그리 매력적인 것만은 아니어서, 적당한 타협안인 'k번째 최단경로'를 구하길 원한다. 그를 돕기..
[알고리즘/그래프] 크루스칼(Kruskal) 최소 신장 트리 vs 다익스트라(Dijksta) 최단 경로
Dot Algo∙ DS/알고리즘 개념 2021. 4. 29. [알고리즘/그래프] 크루스칼(Kruskal) 최소 신장 트리 vs 다익스트라(Dijksta) 최단 경로 그리디 알고리즘 과정 해 선택 실행 가능성 검사 해 검사 크루스칼(Kruskal)과 그리디 알고리즘 최소 신장트리는 사이클을 형성하지 않고 그래프 내의 모든 정점을 최소의 비용으로 연결하는 트리이다. 최소 신장 트리를 구축하는데 한 가지 중요한 제약은 최소 신장 트리 내에 사이클이 형성되어서는 안된다는 것이다. 크루스칼 알고리즘 동작 방식 1) 그래프 내의 모든 간선의 가중치에 대해 오름차순으로 정렬한다. 2) 1)의 간선을 차례대로 순회하면서 최소 신장 트리에 추가한다. (사이클 생성 x) 그리디 과정으로 다시 보면 다음과 같다. 해 선택 : 가장 작은 가중치의 간선 선택 실행 가능성 검사 : 사이클 생성 여부 파악 (사이클 생성되면 x) 해 검사 : 모든 정점이 하나의 집합에 있는지 확인 다익스트라(..
[알고리즘/ 그래프] 벨만 포드 알고리즘 (Bellman-Ford Algorithm) (Java)
Dot Algo∙ DS/알고리즘 개념 2021. 4. 25. [알고리즘/ 그래프] 벨만 포드 알고리즘 (Bellman-Ford Algorithm) (Java) 최단경로 알고리즘 최단 경로 문제는 다음과 같이 분류할 수 있다. 모든 간선이 양수인 경우 음수 간선이 있는 경우 음수 간선 순환은 없는 경우 음수 간선 순환이 있는 경우 위의 분류를 3가지 알고리즘을 통해 구할 수 있다. 벨만포드 알고리즘 (Bellman-Ford Algorithm) → 2-1),2-2) 음수 간선이 있는 경우 다익스트라 알고리즘(Dijkstra Algorithm) → 1)모든 간선 양수 플로이드 와샬 알고리즘(Floyd-Warshall Algorithm) → 1)모든 간선 양수 벨만포드 알고리즘 벨만포드 최단 경로 알고리즘은 음수 간선이 포함된 상황에서의 최단 거리 문제를 풀 때 사용할 수 있다. 또한, 음수 간선의 순환을 감지할 수 있다. 동작 과정 출발 노드를 설정한다. (to, ..

티스토리툴바

티스토리툴바