Algorithm (6) 썸네일형 리스트형 백준 1761번(JAVA) - 정점들의 거리 import java.util.*; import java.io.*; class Node { int v; int w; Node(int v, int w) { this.v=v; this.w=w; } } public class Main { public static ArrayList[] arr; public static int N; public static int[] Depth; // 깊이 public static int[][] parent;// parent[0][3] 은 3번 노드의 2의0승 부모, //parent[5][3]은 3번 노드의 2의 5승부모, 즉 32번째 부모 public static int[][] length;// length[5][3] 은 3번 노드부터 2의0승 부모까지의 길이 public st.. 백준 10217번(JAVA) - KCM Travel, 재채점 후 새로운 풀이 분명히 맞았던 문제인데 갑자기 재채점 되면서 시간초과로 틀렸다. 알고보니 어떤 분이 질문게시판에 예시로 어떤 입력을 보여주면서, 이걸로 하면은 대부분의 코드들이 시간초과가 나온다고 질문글을 올렸고(1년전) 그게 최근에 검토가되서 재채점이 된 것이다. 내 기억이 맞다면 이 문제는 꽤 많은 사람들이 맞춰가지고, 다익스트라 분류로 들어가면 상위권에 노출되던 문제였다. 그런데 재채점 후 저~~ 하위권으로 내려갔을 정도로 재채점 후 많은 분들이 틀렸다 그래서 내 다익스트라를 조금 더 다듬어봤다. import java.util.*; import java.io.*; class Node implements Comparable { int v; int c; int d; Node(int v,int c,int d) { thi.. 백준 1238번(JAVA) 처음에는 어떻게 풀어야 할지 감이 안잡혔다. 일단 왕복거리를 구한다는 것은 알았다. X번에서 각 마을까지의 최소거리는 X번에서 다익스트라를 실시하면 된다. 그럼 각 마을에서 X번까지의 최소거리를 구하기 위해서 1번에서 N번까지(X번을 뺀) 모두 다익스트라를 실시하면 될까? 그렇다면 다익스트라를 총 N번 실행해야 한다. 딱봐도 시간초과의 느낌이 나지않는가? 그래서 생각해낸 방법은 X에서 2번실행하는것이다. 제일 중요한것이 간선을 입력 받을 때 거꾸로도 입력받는것이다. 예를 들어 a에서 b로 가는 가중치w의 간선이 있다면 b에서 a로 가는 가중치w의 간선도 추가해 주는것이다. 자세한 설명은 아래 글에서 잘 설명 되어있다. 꼭 한번 참고해 보길 바란다.steady-coding.tistory.com/106 [B.. 백준 14267번(JAVA) 기본적으로 트리를 생성할 줄 안다면 수월하게 풀 수있다. 나 같은경우에는 ArrayList로 트리를 구현했다. 문제에서는 직속부하와 상사라고 표현했지만 직속부하는 자식 노드, 상사는 부모 노드, 사장은 루트노드라고 생각하고 풀면된다. 우선 부모자식 관계를 입력받는다. 그 후 따로 선언해놓은 int[] result배열에 각각의 칭찬수치를 더한다. 예를들어 2번직원이 2만큼 칭찬받았다면 result[2]=result[2]+2, 3번직원이 4만큼 칭찬받았다면 result[3]=result[3]+4, 이런식으로 그 후 사장노드부터 DFS를 실시하는데 실시할때 부모노드의 result값을 자식노드의 result값에 더한다. 그리고 result를 1부터 n까지 출력하면 끝. 핵심은 DFS를 사장부터 시작하고 부모노드.. 백준 10282번(JAVA) 기본적인 다익스트라 문제이지만 원하는 값은 다르다. 정점의 개수가 주어지고 출발점에서 시작해서 도달 할 수 있는정점은 몇개인지(시작점 포함), 그리고 도달 할 수있는 정점중 가장 거리가 먼것은 몇인지 출력하면된다. 간단하게 일반적인 다익스트라를 실시한다. 일반적인 다익스트라에 관한 문제는 아래에 링크를 걸어두겠다. 2021.04.24 - [백준 문제풀이(JAVA)/그래프] - 백준 1916번(JAVA) 백준 1916번(JAVA) 다익스트라 알고리즘을 이용해 푸는 문제다 저번에 다익스트라를 풀어봤지만 잘 이해가 안되서 중간고사를 끝난 기념으로 한 번 더풀었다. 다익스트라는 뭐랄까 약간 그래프에서의 Bottom-Up 방 red-tiger.tistory.com 단순하게 시작점에서 해당 정점까지의 거리를 나타내.. 백준 1261번(JAVA) 다익스트라를 응용하는 문제이다. BFS와 다익스트라를 모두 다룰줄 안다면 손쉽게 풀 수 있다. 기본 다익스트라를 모를 경우 아래 링크에서 참고하도록 하자. 2021.04.24 - [백준 문제풀이(JAVA)/그래프] - 백준 1916번(JAVA) 백준 1916번(JAVA) 다익스트라 알고리즘을 이용해 푸는 문제다 저번에 다익스트라를 풀어봤지만 잘 이해가 안되서 중간고사를 끝난 기념으로 한 번 더풀었다. 다익스트라는 뭐랄까 약간 그래프에서의 Bottom-Up 방 red-tiger.tistory.com 일반 다익스트라와 다른점을 꼽자면 굳이 연결정보를 안알려준다는 것이다. 나는 단순하게 생각했다. 현재정점의 위,아래,오른쪽,왼쪽은 모두 연결되어있으며 만약 벽이 있다면 가중치가 1,벽이 없다면 가중치가 0.물론.. 이전 1 다음
