개발블로그by페페

depth 정보와 parent 정보 필요 > TP 정보 및 BFS로 공급해줄것 일반 BFS 흐름에 patch 부착 (pairing) - depth - parent parent는 connected와 now 관계로 바로 공급 가능 다만 root는 0으로 depth를 잡고 root아닌, root와 연결된 바로 다음 노드부터 depth정보를 공급하므로, sP - 지금 root(depth가 0인 노드갯수) 1 충족 - 다음 node의 depth = 1 depth가 1인 과거 노드갯수 queue.size() 충족 > 즉 queue.poll()로 다 빠져나갔을 때 > 다음 depth는 카운터를 올린다

단순 에지 순회만 하는 bellman-ford는 - queue 대신 Edge[] 를 사용 - Edge(s, e, w) class 공급하나 Comparable 넣지않음 MSP는 - PQ 사용 - Edge class(s, e, w) 공급 및 w 기반 Comaparble 역시 사용 Topology Sort는 - ArrayList로 []접근하지 않고 V만큼 ArrayList() 초기화 공급 - get으로 access DFS, BFS는 - ArrayList[] 로 양방향 노드 더하기 Dijkstra는 - ArrayList[]로 특정 노드에 연결된 '다음 노드 + distance' TP 정보를 공급 - 최단거리부터 갱신해야하므로 w 기반 PQ도 필요하다 - sP 필요 sP 작업 필요 에지가 여러개 있을 수 있으므로..

우선순위는 필요없으나 에지중심 작업이므로 s와 e, 그리고 사이인 w를 사용할 Edge class 필요 MSP처럼 최소거리부터 연결하기 위해 정렬시킬 필요가 있을 때에는 PQ에 에지를 (모두)넣고 (BFS없이)빼야 하지만 순서없이 단순히 모든 에지를 순회시켜 check-in으로 충분한 경우에는 Edge를 기반으로 하는 List만 만들고 넣어준다 receiver 필요 1이 sP이므로 0 설정 첫번째 for문은 단순반복이므로 while으로 대체하는게 편할수도 있다 모든 에지를 순회하되, 시작부터 INF 되는것은 거른다 크다 > 작다 에서 큰것 = 작은것 으로 할당 surviving boolean으로 return이 아닐 때에는 cont가 필요하다 더 작은 거리가 발생만 하면 변경작업 없이 바로 boolean으..

에지 거리 값을 넣기 전에, 에지가 없을 수도 있으므로 초기화를 해준다 - 모든 노드와 노드 사이를 출력해야 하므로 import java.util.Scanner; public class Main { public static void main(String[] args) { // ISC Scanner sc = new Scanner(System.in); int V = sc.nextInt(); int E = sc.nextInt(); // TP int[][] TP = new int[V+1][V+1]; for (int i = 1; i

작은것부터 연결해야 하기 때문에 - 54321 정배열 PriorityQueue - 배열의 기준을 잡으려고(w) compareTo 필요 * 인식자에서 queue에 바로 넣어버리므로 별도 TP list는 필요하지 않음 (넣자마자 자동 정렬됨) union은 이미 check-in 되었다는 phaser로 사용됨 노드가 3개라면 모두 연결된 에지는 2(V-1)개이다 그래서 while공간이 1 > 2를 모두 순회하고 3은 진입하지 않는다 import java.util.PriorityQueue; import java.util.Scanner; public class Main { static int[] parent; public static void main(String[] args) { // ISC Scanner sc ..

ArrayList - capacity를 별도로 정하지 않고 - 1~V번 new ArrayList()를 add한다 []처럼 순차 pointer(i)가 없으므로, get(s)를 사용하여 access 그리고 add를 더함 또 순서가 있으므로 배열과 달리 단방향만 더해주면 된다 TP와 별도로 Field인 Queue가 필요 * 에지 가중치가 아닌, 에지 양 끝 노드의 순서이고 순서 정보는 indegree로 공급받으므로 pQ는 필요없다 *통상 OP시 개설해도 되지만, indegree가 0인것을 먼저 넣고 시작해야 하므로(sP) 미리 개설 후 sP 유입까지 끝내둔다 indegree가 0인 (동일 위상 내) 무더기 작업이 끝나고 다음 작업이 필요하므로 BFS를 사용한다(DFS와 대조하여) sP는 위에서 작업했으므로, ..

Cont - 초기화 - D2TP TP[i] 하나하나가 ArrayList이므로 for문으로 sort해줘야 한다 DFS pairing - divergence - phaser now + connected 진입시 phaser 체크됨 BFS는 DFS와 여러 차이점이 있는데 - 재귀가 아닌 Field필요하여 Queue 생성 - 처음 진입한 것은 sP로 별도 인식 나오는 now와 들어가는 connected를 pairing함 - 진입할때 phaser 체크됨 import java.util.*; public class Main { static ArrayList[] TP; static boolean[] visited; public static void main(String[] args) { // ISC Scanner sc ..

plate를 만들고 - 쏴준다 그사이 OP + receiver로 plate를 사용한다 line을 String[] set으로 나눈다 char[]는 하면 안됨 "[+]" 기준으로 split String이므로 Int로 Parsing해줄것 "-" 기준으로 split Sum 작업 맡기기(plate로 리턴됨) 0이면 더하고 나머지 다 빼기 import java.util.Scanner; public class Main { static int plate = 0; public static void main(String[] args) { // ISC Scanner sc = new Scanner(System.in); String str = sc.nextLine(); // D2F String[] set = str.split(..

Priority // 5, 4, 3, 2, 1 // -1, -2, -3, -4, -5 Priority reversal // 1 2 3 4 5 // -5. -4. -3. -2. -1 D2F는 container 공간이 먼저 필요 그다음 나눠서 delivery 1 이상 위상공간에서는 모두 곱셈작업이 일어난다 계산은 recursive bottom처럼 마지막에만 생각하면 됨 - 3이 남거나 - 2가 남거나 pq는 그냥 더해주면 되고, mq는 0이 있으면 곱해서 없앰 - import java.util.Collections; import java.util.PriorityQueue; import java.util.Scanner; public class Main { public static void main(String..