본문 바로가기

다익스트라12

[자바] 백준 1584 - 게임 (java) 목차 문제 : boj1584 필요 알고리즘 0-1 너비 우선 탐색 (0-1 bfs), 다익스트라 (dijkstra) 간선이 0 또는 1일 경우에 대한 문제이다. 다익스트라로도 풀 수 있고, 0-1 bfs를 쓰면 더 효율적으로 가능하다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 맵의 각 지점의 상태는 안전, 위험, 죽음 이다. 죽음은 아예 안가면 되므로 딱히 상관없다. 안전과 위험만 보면 되는데, 안전은 가중치가 0인 셈.. 2023. 12. 1.
[자바] 백준 23807 - 두 단계 최단 경로 3 (java) 문제 : boj23807 필요 알고리즘 개념 다익스트라, 브루트포스 다익스트라로 거리를 구하고, 세 개의 정점은 브루트포스로 고를 수 있다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 이 문제에서 중요한건 시작점 x, 목표지점인 z, 그리고 P개의 중간정점 중 3개를 지나야 한다는 점이다. 아주 간단하게 생각해보자. x에서 출발해 P개의 중간정점까지의 최단 거리를 모두 안다고 해보자. 그리고 P개의 중간정점에서 중간정점들.. 2023. 3. 1.
[자바] 백준 11779 - 최소비용 구하기 2 (java) 문제 : boj11779 필요 알고리즘 개념 다익스트라 (dijkstra) 다익스트라 응용 문제이다. 기본적인 다익스트라 구현방법은 알아야 풀 수 있고, 추가로 경로를 구할 방법도 생각해봐야 한다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 다익스트라 공부용으로 추천하는 문제이다. 1854번 - K번째 최단 경로도 매우 추천한다. 다익스트라의 진행 경로를 출력해줘야 하는 문제이다. 처음엔 좀 당황스러웟는데, 반대로 목적지.. 2022. 9. 30.
[ABC252] E - Road Reduction (AtCoder Beginner Contest 252 in Java) 문제 : abc252_e 다익스트라 자료구조에 대해 이해를 하고있다면 쉽게 풀 수 있다. 문제에서 제시된 d2+d3+...+dN의 합을 최소화 한다는 말은 즉, 1부터 모든 정점으로의 최단거리를 가지는 N-1개의 edge를 남겨야 한다는 말과 동일하다. 1부터 모든 정점으로의 최단거리는 다익스트라를 돌리면 얻을 수 있고, 다익스트라의 결과는 모든 정점으로의 경로가 존재했다면 N-1개만 남게 된다. 그러므로, 단순히 정점 1부터 시작하는 다익스트라를 구현하고, 이 때 각 정점으로 마지막으로 들어왔던 간선(즉, 각 정점으로 들어온 1부터 최단거리에 해당하는 간선)을 저장해둔 후 그걸 출력해주면 된다. 이 때 'in arbitrary order' 라고 했으므로(랜덤 순서를 뜻한다) 아무 순서로든 출력만 해주면.. 2022. 5. 22.
[자바] 백준 10979 - 가넷이나 버는게 낫지 않아요? 문제 : boj10979 이하의 질문글을 보고 궁금해서 풀어보려다가 물렸다... 결국 31회의 시도로 개인 최장 시도횟수를 찍었고, 결국 뚫긴 했다. 10시간 넘게 걸렸다. 다른 분들 시도횟수까지 포함하면 자바 제출 시도 60회 만에 첫 통과이다 ㅋㅋㅋ 1. 자바로 풀 때 이 문제를 위한 메모리 최적화 일단 이게 자바로는 Scanner는 애초에 느려서 못쓰고, 많이들 사용하는 BufferdReader로 입력받는 순간 메모리 초과가 뜬다. 이게 BufferdReader가 미리 버퍼를 두고 더 많은 양을 미리 입력받아두기 때문에 그렇다. 일반적으로는 그정도론 문제가 없는데 이 문제는 메모리 제한이 너무 낮아 일단 그것만으로도 메모리 초과가 되는 것이다. BufferedReader 생성자 중 두 번째 para.. 2022. 4. 23.
[자바] 백준 1854 - K번째 최단경로 찾기 문제 : boj1854 다익스트라에 대한 이해를 높히고 으용하는데 매우 도움되는 문제이다. 강추! (플로이드 와샬 이해에는 23258번 밤편지 강추) 다른 문제 풀다가 2번째 최단경로를 찾아야 하는 경우가 있어 찾아보다가 이 문제도 풀게됬다. 다익스트라를 돌릴 때 1부터 n까지 가는 최소 가중치를 알려고 한다고 해보자. 이 때, n번에 처음 도착 했을 때 바로 답을 출력하면 될까? 가중치가 동일한 bfs와 달리 다익스트라는 가중치가 있을 때 사용하기 때문에 그러면 안된다. 다익스트라는 priority queue가 빌 때 까지 다 해봐야 답이 나온다. 그럼 2번째로 작은 가중치를 가지는 경로를 어떻게 구할 수 있을까? 어떠한 정점에 도달한 기록을 2개 유지하면 된다. 물론 이 때에도 마찬가지로 원하는 위치.. 2022. 4. 23.
백준 1486 자바 - 등산 (boj 1486 java) 문제 : boj1486 ※ 블로그 만들기 이전에 깃헙에 텍스트로만 작성해둔 풀이라 그림도 없고 다른 글들과 말투가 다릅니다. 날잡고 옮겨야지 생각은 했는데 블로그 만들기 이전에 푼게 900개정도 이기도 하고, 요즘 푸는거 풀이 작성하기도 빡쌔므로 아무래도 전부 새로 작성해서 옮길 시간을 없을 것 같아서 틈틈히 그냥 깃헙에 적어둔 텍스트로만 된 풀이라도 옮겨둘 생각입니다. 모든 위치에서 시작할 수 있는게 아니고, 딱 0,0 지점에서 출발이 가능하므로 결국 0,0에서 모든 지점으로의 거리와 모든 지점에서 0,0으로의 거리를 알면 solution 함수처럼 D 이내의 왔다가 다시 오는 거리 중 가장 높이가 높은걸 찾으면 됨. 그럼 결국 위에서 말한 2가지만 구할 수 있으면 되는데, 플로이드 와샬로 한방에 구해도.. 2022. 4. 5.
백준 4485 자바 - 녹색 옷 입은 애가 젤다지? (BOJ 4485 JAVA) 문제 : boj4485 1. 젤다가 활강하는 장면! 야숨2가 나오면 알고리즘을 당분간 못(안)풀 수 있으니 알고리즘을 미리 풀고 키핑해둬야겠다ㅋㅋㅋ 2. 만약 이런식의 문제에서 이동 가능한게 좌측과 아래쪽 뿐이었다면 DP로도 풀 수 있다. 하지만 이 문제와 같이 4방향으로 이동이 가능하다면, DP로 풀어보려면 결국 모든 경우를 다 봐야해서 시간초과가 나게 될 것이다. O((N^2)^2) 한가지 떠올릴만한 점은 결국 배열도 그래프라는 것이다. 예제 입력의 아래와 같은 부분을 그래프 형태로 그려보면 다음과 같다. 3 5 5 4 3 9 1 3 2 7 결국 이 문제는 가장 적게 잃으면서 진행해야 하므로, 그냥 그래프에서 start부터 goal 까지의 최단거리를 찾는 것과 동일하다! 그리고 가중치가 모두 양수이면.. 2021. 12. 24.
백준 12834 자바 - 주간 미팅 (BOJ 12834 JAVA) 문제 : boj12834 문제의 입력 최대값 제한에 자비심이 넘치는 문제이다. 사실상 Floyd-Warshall만 딱 못쓰게 제한 걸고(V 2021. 12. 16.
백준 22865 자바 - 가장 먼 곳 (BOJ 22865 JAVA) 문제 : boj22865 설명이 좀 부족한 부분이 있는 문제이다. 일단 문제 이해부터 해보자. 예제 입력 1을 그래프로 그려보면다음과 같다. 위 그래프를 기반으로 어떠한 X 지점에서 시작해서 모든 정점으로 가는 최단거리를 구해보겠다. 이 때, 시작하는 정점인 X는 각각 A,B,C 이다. 예를들어 C인 5번 정점에서 시작할 경우 3번정점까지의 최단거리는 '7'이다. A,B,C로의 거리를 알아야 하는데 왜 A,B,C에서 시작하는 거리를 잰 것인지 궁금할 수 있다. 이 문제의 경우 무방향 그래프에서 진행되므로, A에서 모든 정점으로 가는 최단거리는 모든 정점에서 A로 가는 최단거리와 동일하다. 문제에서 미흡한 부분이, X가 A,B,C가 될 수 있는지 없는지 명확히 제시하지 않았다는 점이다(어차피 시작점들은 거.. 2021. 12. 7.

티스토리툴바