10월이 거의 끝나간다. 24년도 100일이 채 남지 않았다. 곧 서른인데... ☹️ 이번 주 뭘 했나 10월의 넷째 주를 되돌아본다.
순공 시간을 길게 잡지 못하고있다. 집중력이 많이 안 좋다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
public static void main(String[] args) {
new Main().run();
}
private void run() {
try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in))) {
Solution s = new Solution();
System.out.println(s.solution(readInput(br)));
} catch (IOException e) {
throw new RuntimeException(e);
}
}
private List<List<Integer>> readInput(BufferedReader br) throws IOException {
String[] tokens = br.readLine().split(" ");
int numOfNodes = Integer.parseInt(tokens[0]);
int numOfLinks = Integer.parseInt(tokens[1]);
List<List<Integer>> result = new ArrayList<>();
for (int i = 0; i < numOfNodes + 1; i++) {
result.add(new ArrayList<>());
}
for (int i = 0; i < numOfLinks; i++) {
tokens = br.readLine().split(" ");
int from = Integer.parseInt(tokens[0]);
int to = Integer.parseInt(tokens[1]);
result.get(from).add(to);
}
return result;
}
}
class Solution {
public String solution(List<List<Integer>> graph) {
StringBuilder answer = new StringBuilder();
int[] indegree = getIndegree(graph);
PriorityQueue<Integer> q = new PriorityQueue<>();
for (int i = 1; i < indegree.length; i++) {
if(indegree[i] == 0) q.offer(i);
}
while (!q.isEmpty()) {
int cur = q.poll();
answer.append(cur).append(" ");
for (Integer next : graph.get(cur)) {
indegree[next]--;
if(indegree[next] == 0) q.offer(next);
}
}
return answer.toString();
}
private int[] getIndegree(List<List<Integer>> graph) {
int len = graph.size();
int[] indegree = new int[len];
for (int i = 1; i < len; i++) {
List<Integer> node = graph.get(i);
for (Integer next : node) {
indegree[next]++;
}
}
return indegree;
}
}
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
public static void main(String[] args) {
new Main().run();
}
private void run() {
try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in))) {
Input ip = readInput(br);
Solution s = new Solution();
System.out.println(s.solution(ip.costs, ip.graph));
} catch (IOException e) {
throw new RuntimeException(e);
}
}
private Input readInput(BufferedReader br) throws IOException {
int len = Integer.parseInt(br.readLine());
int[] costs = new int[len + 1];
List<List<Integer>> graph = new ArrayList<>();
for (int i = 0; i < len + 1; i++) {
graph.add(new ArrayList<>());
}
for (int i = 0; i < len; i++) {
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
int cost = Integer.parseInt(st.nextToken());
costs[i + 1] = cost;
while (st.hasMoreTokens()) {
int value = Integer.parseInt(st.nextToken());
if(value == -1) break;
graph.get(value).add(i + 1);
}
}
return new Input(costs, graph);
}
private static class Input {
private final int[] costs;
private final List<List<Integer>> graph;
public Input(int[] costs, List<List<Integer>> graph) {
this.costs = costs;
this.graph = graph;
}
}
}
class Solution {
public String solution(int[] costs, List<List<Integer>> graph) {
int[] indegree = getIndegree(graph);
int[] dp = Arrays.copyOfRange(costs, 0, costs.length);
Queue<Integer> q = new ArrayDeque<>();
for (int i = 1; i < indegree.length; i++) {
if(indegree[i] == 0) q.offer(i);
}
while (!q.isEmpty()) {
int cur = q.poll();
for (Integer next : graph.get(cur)) {
if (dp[next] < dp[cur] + costs[next]) {
dp[next] = dp[cur] + costs[next];
}
indegree[next]--;
if(indegree[next] == 0) q.offer(next);
}
}
return getAnswer(dp);
}
private int[] getIndegree(List<List<Integer>> graph) {
int len = graph.size();
int[] indegree = new int[len];
for (int i = 1; i < len; i++) {
List<Integer> node = graph.get(i);
for (Integer next : node) {
indegree[next]++;
}
}
return indegree;
}
private String getAnswer(int[] dp) {
StringBuilder answer = new StringBuilder();
for (int i = 1; i < dp.length; i++) {
answer.append(dp[i]).append("\n");
}
return answer.toString();
}
}
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
public static void main(String[] args) {
new Main().run();
}
private void run() {
try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in))) {
Solution s = new Solution();
System.out.println(s.solution(readInput(br)));
} catch (IOException e) {
throw new RuntimeException(e);
}
}
private List<List<Integer>> readInput(BufferedReader br) throws IOException {
String[] tokens = br.readLine().split(" ");
int numOfNodes = Integer.parseInt(tokens[0]);
int repeat = Integer.parseInt(tokens[1]);
List<List<Integer>> result = new ArrayList<>();
for (int i = 0; i < numOfNodes + 1; i++) {
result.add(new ArrayList<>());
}
for (int i = 0; i < repeat; i++) {
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
st.nextToken();
int from = 0;
int value = 0;
while (st.hasMoreTokens()) {
if (from == 0) {
from = Integer.parseInt(st.nextToken());
value = Integer.parseInt(st.nextToken());
} else {
value = Integer.parseInt(st.nextToken());
}
result.get(from).add(value);
from = value;
}
}
return result;
}
}
class Solution {
public String solution(List<List<Integer>> graph) {
StringBuilder answer = new StringBuilder();
int[] indegree = getIndegree(graph);
Queue<Integer> q = new ArrayDeque<>();
for (int i = 1; i < indegree.length; i++) {
if(indegree[i] == 0) q.offer(i);
}
int cnt = 0;
while (!q.isEmpty()) {
int cur = q.poll();
cnt++;
answer.append(cur).append("\n");
for (Integer next : graph.get(cur)) {
indegree[next]--;
if(indegree[next] == 0) q.offer(next);
}
}
if (cnt == graph.size() - 1) {
return answer.toString();
}
return "0";
}
private int[] getIndegree(List<List<Integer>> graph) {
int len = graph.size();
int[] indegree = new int[len];
for (int i = 1; i < len; i++) {
for (Integer next : graph.get(i)) {
indegree[next]++;
}
}
return indegree;
}
}
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Comparator;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) {
new Main().run();
}
private void run() {
try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in))) {
Input ip = readInput(br);
Solution s = new Solution();
System.out.println(s.solution(ip.numOfComputers, ip.wires));
} catch (IOException e) {
throw new RuntimeException(e);
}
}
private Input readInput(BufferedReader br) throws IOException {
int numOfComputers = Integer.parseInt(br.readLine());
int numOfWires = Integer.parseInt(br.readLine());
int[][] wires = new int[numOfWires][3];
for (int i = 0; i < numOfWires; i++) {
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
int from = Integer.parseInt(st.nextToken());
int to = Integer.parseInt(st.nextToken());
int cost = Integer.parseInt(st.nextToken());
wires[i][0] = from;
wires[i][1] = to;
wires[i][2] = cost;
}
return new Input(numOfComputers, wires);
}
private static class Input{
private final int numOfComputers;
private final int[][] wires;
public Input(int numOfComputers, int[][] wires) {
this.numOfComputers = numOfComputers;
this.wires = wires;
}
}
}
class Solution {
public int solution(int numOfComputers, int[][] wires) {
Arrays.sort(wires, Comparator.comparing(a -> a[2]));
int[] group = initGroup(numOfComputers);
int cnt = 0;
int sumOfCosts = 0;
for (int[] wire : wires) {
if(cnt == numOfComputers - 1) break;
int from = wire[0];
int to = wire[1];
if(isSameGroup(group, from, to)) continue;
connect(group, from, to);
sumOfCosts += wire[2];
}
return sumOfCosts;
}
private int[] initGroup(int numOfComputers) {
int[] result = new int[numOfComputers + 1];
for (int i = 0; i < numOfComputers + 1; i++) {
result[i] = i;
}
return result;
}
private boolean isSameGroup(int[] group, int target1, int target2) {
return getGroup(group, target1) == getGroup(group, target2);
}
private int getGroup(int[] group, int target) {
if(target != group[target]) group[target] = getGroup(group, group[target]);
return group[target];
}
private void connect(int[] group, int target1, int target2) {
int group1 = getGroup(group, target1);
int group2 = getGroup(group, target2);
group[Math.max(group1, group2)] = Math.min(group1, group2);
}
}