본문 바로가기

Dijkstra

[BOJ] 백준 1238번 파티 (Java)
Dot Algo∙ DS/PS 2021. 5. 19. [BOJ] 백준 1238번 파티 (Java) #1238 파티 난이도 : 골드 3 유형 : 그래프 이론/ 다익스트라(권장) || 플로이드 와샬 1238번: 파티 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어 www.acmicpc.net ▸ 문제 N개의 숫자로 구분된 각각의 마을에 한 명의 학생이 살고 있다. 어느 날 이 N명의 학생이 X (1 ≤ X ≤ N)번 마을에 모여서 파티를 벌이기로 했다. 이 마을 사이에는 총 M개의 단방향 도로들이 있고 i번째 길을 지나는데 Ti(1 ≤ Ti ≤ 100)의 시간을 소비한다. 각각의 학생들은 파티에 참석하기 위해 걸어가서 다시 ..
[BOJ] 백준 1261번 알고스팟 (Java)
Dot Algo∙ DS/PS 2021. 5. 15. [BOJ] 백준 1261번 알고스팟 (Java) #1261 알고스팟 난이도 : 골드 4 유형 : 그래프 탐색/ BFS/ Dijkstra(우선순위 큐) 1261번: 알고스팟 첫째 줄에 미로의 크기를 나타내는 가로 크기 M, 세로 크기 N (1 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 미로의 상태를 나타내는 숫자 0과 1이 주어진다. 0은 빈 방을 의미하고, 1은 벽을 의미 www.acmicpc.net ▸ 문제 알고스팟 운영진이 모두 미로에 갇혔다. 미로는 N*M 크기이며, 총 1*1크기의 방으로 이루어져 있다. 미로는 빈 방 또는 벽으로 이루어져 있고, 빈 방은 자유롭게 다닐 수 있지만, 벽은 부수지 않으면 이동할 수 없다. 알고스팟 운영진은 여러명이지만, 항상 모두 같은 방에 있어야 한다. 즉, 여러 명이 다른 방에 있을 수는 없다. ..
[알고리즘/ 그래프] 다익스트라(Dijkstra) vs 플로이드 와샬(Floyd Warshall) (JAVA)
Dot Algo∙ DS/알고리즘 개념 2021. 3. 5. [알고리즘/ 그래프] 다익스트라(Dijkstra) vs 플로이드 와샬(Floyd Warshall) (JAVA) 다익스트라(Dijkstra) vs 플로이드 와샬(Floyd Warshall) Dijkstra 알고리즘은 하나의 정점에서 출발했을 때 다른 모든 정점으로의 최단 경로를 구하는 알고리즘이다. 그에 반해 Floyd Warshall 알고리즘은 모든 정점에서 다른 모든 정점으로의 최단 경로를 구하는 알고리즘이다. Dijkstra 알고리즘은 매번 가장 적은 비용을 가진 노드를 하나씩 꺼낸 다음 그 노드를 거쳐가는 비용, 즉 가장 적은 비용을 하나씩 선택하는 로직으로 구성되었다면, Floyd Warshall 알고리즘의 핵심 아이디어는 애초에 거쳐가는 정점을 하나씩 다 설정을 하여 직접 확인하는 방법, 즉 거쳐가는 정점을 기준으로 최단 거리를 구하도록 구성되어있다. 다익스트라(Dijkstra) 알고리즘 다익스트라의 최..

티스토리툴바

티스토리툴바