전체 글 검색 결과

해당 글 141건

백준 10282번(JAVA)

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

백준 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)/다익스트라 2021. 4. 27. 02:02

백준 1261번(JAVA)

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

백준 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)/다익스트라 2021. 4. 25. 14:53

백준 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)/다익스트라 2021. 4. 24. 19:33