백준 문제풀이(JAVA)다익스트라 검색 결과

해당 글 7건

백준 13907번(JAVA)-세금

2차원 DP를 활용한 다익스트라 문제이 import java.util.*; import java.io.*; class Node implements Comparable { int v; int w; int c; Node(int v,int w,int c) { this.v=v; this.w=w; this.c=c; } public int compareTo(Node o) { return w-o.w; } } public class Main { public static int[][] dp; public static int N; public static int S; public static int D; public static void main(String[] args) throws IOException{ // TODO..
백준 문제풀이(JAVA)/다익스트라 2년 전

백준 1238번(JAVA)

처음에는 어떻게 풀어야 할지 감이 안잡혔다. 일단 왕복거리를 구한다는 것은 알았다. X번에서 각 마을까지의 최소거리는 X번에서 다익스트라를 실시하면 된다. 그럼 각 마을에서 X번까지의 최소거리를 구하기 위해서 1번에서 N번까지(X번을 뺀) 모두 다익스트라를 실시하면 될까? 그렇다면 다익스트라를 총 N번 실행해야 한다. 딱봐도 시간초과의 느낌이 나지않는가? 그래서 생각해낸 방법은 X에서 2번실행하는것이다. 제일 중요한것이 간선을 입력 받을 때 거꾸로도 입력받는것이다. 예를 들어 a에서 b로 가는 가중치w의 간선이 있다면 b에서 a로 가는 가중치w의 간선도 추가해 주는것이다. 자세한 설명은 아래 글에서 잘 설명 되어있다. 꼭 한번 참고해 보길 바란다.steady-coding.tistory.com/106 [B..
백준 문제풀이(JAVA)/다익스트라 4년 전

백준 10282번(JAVA)

기본적인 다익스트라 문제이지만 원하는 값은 다르다. 정점의 개수가 주어지고 출발점에서 시작해서 도달 할 수 있는정점은 몇개인지(시작점 포함), 그리고 도달 할 수있는 정점중 가장 거리가 먼것은 몇인지 출력하면된다. 간단하게 일반적인 다익스트라를 실시한다. 일반적인 다익스트라에 관한 문제는 아래에 링크를 걸어두겠다. 2021.04.24 - [백준 문제풀이(JAVA)/그래프] - 백준 1916번(JAVA) 백준 1916번(JAVA) 다익스트라 알고리즘을 이용해 푸는 문제다 저번에 다익스트라를 풀어봤지만 잘 이해가 안되서 중간고사를 끝난 기념으로 한 번 더풀었다. 다익스트라는 뭐랄까 약간 그래프에서의 Bottom-Up 방 red-tiger.tistory.com 단순하게 시작점에서 해당 정점까지의 거리를 나타내..
백준 문제풀이(JAVA)/다익스트라 4년 전

백준 11779번(JAVA)

이번 문제는 다익스트라 알고리즘에다가 되추적까지 해줘야 하는 문제다. 문제의 조건에는 안나와있지만 정점은 1번부터n번이다. 기본적으로 다익스트라와 동일하다. 단, 되추적을 위해 int[] before 배열을 선언한다 예를들어 최단거리 경로가 1번에서 3번으로 가기위한 최단 경로가 1->2->3일경우 before[3]=2, before[2]=1을 집어넣는다. 되추적은 일단 index를 end로 잡는다 그리고 루프를 돌면서 index를 스택에 넣고 index=before[index] 실시하고 count값을 증가시켜준다. 만약 index가 start가면 루프를 깬다. count값을 출력하고 stack이 빌 때까지 계속 출력해주면 된다. stack에는 처음에 index를 집어넣으면 end가 들어가고 마지막에는 ..
백준 문제풀이(JAVA)/다익스트라 4년 전

백준 1261번(JAVA)

다익스트라를 응용하는 문제이다. BFS와 다익스트라를 모두 다룰줄 안다면 손쉽게 풀 수 있다. 기본 다익스트라를 모를 경우 아래 링크에서 참고하도록 하자. 2021.04.24 - [백준 문제풀이(JAVA)/그래프] - 백준 1916번(JAVA) 백준 1916번(JAVA) 다익스트라 알고리즘을 이용해 푸는 문제다 저번에 다익스트라를 풀어봤지만 잘 이해가 안되서 중간고사를 끝난 기념으로 한 번 더풀었다. 다익스트라는 뭐랄까 약간 그래프에서의 Bottom-Up 방 red-tiger.tistory.com 일반 다익스트라와 다른점을 꼽자면 굳이 연결정보를 안알려준다는 것이다. 나는 단순하게 생각했다. 현재정점의 위,아래,오른쪽,왼쪽은 모두 연결되어있으며 만약 벽이 있다면 가중치가 1,벽이 없다면 가중치가 0.물론..
백준 문제풀이(JAVA)/다익스트라 4년 전

백준 1504번(JAVA)

다익스트라 알고리즘을 응용하는 문제이다. 말이 응용이지 그냥 다익스트라를 3번 써주면 된다. 우선 기본적인 다익스트라 알고리즘을 알아야 한다. 혹시 모르는 분들은 이전 포스팅을 참고하길 바란다. 2021.04.24 - [백준 문제풀이(JAVA)/그래프] - 백준 1916번(JAVA) 백준 1916번(JAVA) 다익스트라 알고리즘을 이용해 푸는 문제다 저번에 다익스트라를 풀어봤지만 잘 이해가 안되서 중간고사를 끝난 기념으로 한 번 더풀었다. 다익스트라는 뭐랄까 약간 그래프에서의 Bottom-Up 방 red-tiger.tistory.com 문제는 간단하다. 1번부터 시작해서 N번까지의 최단경로를 구하라. 단, 특정 두 정점을 거쳐야 한다. 특정정점을 A,B라고 하면 2가지 경로가 있다 1번 -> A->B->..
백준 문제풀이(JAVA)/다익스트라 4년 전

백준 1916번(JAVA)

다익스트라 알고리즘을 이용해 푸는 문제다 저번에 다익스트라를 풀어봤지만 잘 이해가 안되서 중간고사를 끝난 기념으로 한 번 더풀었다. 다익스트라는 뭐랄까 약간 그래프에서의 Bottom-Up 방식으로 푸는 DP문제 같다. 내가 생각하는 핵심은 딱 4가지다. 출발지에서의 거리가 가장짧은것이 우선순위가 높게 우선순위큐를 구현해준다. 이때 우선순위 큐는 정수형이 아닌 Node객체를 넣을 수 있게 구현한다. 거리 배열을 따로만들며. 시작점은 0으로 나머지는 가장큰수로 초기화해준다 시작점에서 시작해서 BFS를 실시한다. BFS시 정점A에서 B로 갈때 만약 B가 방문된적없고 dis[B]>dis[A]+A에서B로가는 가중치 일경우 dis[B]=dis[A]+A에서 B로 가는 가중치 로 갱신해주고 우선순위 큐에 B정점과,di..
백준 문제풀이(JAVA)/다익스트라 4년 전