백준 문제풀이(JAVA) (26) 썸네일형 리스트형 백준 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->.. 백준 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.. 이전 1 2 3 4 다음