SH

https://www.acmicpc.net/problem/1238 다익스트라 문제그래프가 단방향이므로, X에 가는 경우와 갔다가 돌아오는 경우 두 번을 탐색해야 한다. 접근법 1. 돌아오는 경로 X -> ALL 탐색을 한 번 한다.2. 가는 경로 모든N -> ALL 탐색을 N번 한다. import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.ArrayList;import java.util.Arrays;import java.util.List;import java.util.PriorityQueue;import java.util.StringTokenizer;class Main ..

https://www.acmicpc.net/problem/1240 일반적인 그래프탐색 문제다. 플로이드-워셜도 시간복잡도 아슬하게 적용 가능하다.(단, 트리이므로 경로가 유일해서 최단 경로 알고리즘은 비효율적이다.) 그래프 탐색간 틀린 이유cost[][] 배열을 썼는데, 메모리 제한이 짠 문제여서 초과함 (경로가 유일하므로 min cost 배열 필요 없음) 풀이 1. BFSimport java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.ArrayDeque;import java.util.ArrayList;import java.util.List;import java.util.Queu..

https://www.acmicpc.net/problem/1132 기본 아이디어1. 알파벳별로 자릿수 가중치를 기록한다. (dp로 기록했는데, 하나의 변수만 써도 충분할 것 같다.)2. 가중치가 높은 순서대로 9, 8, ... 1을 곱해서 정답에 더한다. (그리디)  0으로 시작하는 수는 없다. 이 조건을 "입력에 0으로 시작하는 수는 주어지지 않는다."로 잘못 해석했다.문제의 의도는 "0으로 시작하는 수는 사용하면 안된다." 이다. (예제랑 입력 조건으로 유추가능) 기댓값이 높은 것부터 탐색하면, 0만 남았을 때 0을 쓸 수 없으면(앞자리가 0인 수가 존재하게 되면) 답이 아니게 된다. 따라서, 기댓값이 낮은 것부터 탐색하는게 낫다. 나는 조건을 잘못봐서 전처리로 0체크만 따로 추가했다. (그래서 스파..

https://www.acmicpc.net/problem/1068 트리에서 노드를 하나 끊었을 때 리프 노드의 개수를 구하는 문제 1. 루트 노드 정하기트리에서 부모가 없는 노드는 유일하며, 루트 노드가 된다 (루트 노드를 어디로 잡냐에 따라 리프 노드 개수 또한 달라진다.)(어디던 루트로 잡아도 되지않나 해서 모호했는데, 문제에서 "연결된 노드" 가 아니라 "부모 노드" 목록이 주어진다.) 2. 노드 끊는법 정하기단순히 방문처리(vst[REMOVE] = true)한다.이러면 끊은 노드 및 서브 트리를 방문하지 않게된다. + 문제에선 한 개의 노드만 끊는다. 3. 리프 노드 기준 정하기vst[next] = false 일 때만 다음 탐색을 진행한다.다음 탐색을 한 번도 하지 않았다면 이는 곧 리프 노드다...