📙 Algorithm Solving/Java
📙[Algo] 24.04.08 알고리즘
혜덕hyeduck
2024. 4. 9. 10:43
알고리즘 문제) BOJ 11725. 트리의 부모 찾기
문제 요약
- 루트 없는 트리가 주어진다.
- 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성
시간 제한
- 1초
입력
- 노드의 개수 N
- 2≤N≤10만
- N-1개 줄에 간선 정보 주어짐 (연결된 두 노드 번호)
출력
- 각 노드의 부모 노드 번호를 2번 노드부터 한 줄씩 순서대로 출력
코드
import java.io.*;
import java.util.*;
public class Main {
static int N;
static ArrayList<Integer>[] list;
static int[] parent;
static void dfs(int cur, int prv) {
for (Integer nxt : list[cur]) {
if (nxt == prv) continue;
parent[nxt] = cur;
dfs(nxt, cur);
}
}
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st;
N = Integer.parseInt(br.readLine());
list = new ArrayList[N + 1];
for (int i = 0; i < N + 1; i++) {
list[i] = new ArrayList<>();
}
int node1, node2;
for (int i = 0; i < N - 1; i++) {
st = new StringTokenizer(br.readLine());
node1 = Integer.parseInt(st.nextToken());
node2 = Integer.parseInt(st.nextToken());
list[node1].add(node2);
list[node2].add(node1);
}
parent = new int[N + 1];
dfs(1, 0);
StringBuilder sb = new StringBuilder();
for (int i = 2; i <= N; i++) {
sb.append(parent[i] + "\\n");
}
bw.write(String.valueOf(sb));
bw.flush();
bw.close();
br.close();
}
}
알고리즘 문제) BOJ 15681. 트리와 쿼리
문제 요약
- 가중치와 방향성이 없는 임의의 루트 있는 트리가 주어졌을 때
- 정점 U를 루트로 하는 서브트리에 속한 정점의 수를 출력
시간 제한
- 1초
입력
- 트리의 정점의 수 N과 루트의 번호 R, 쿼리의 수 Q가 주어진다. (2 ≤ N ≤ 105, 1 ≤ R ≤ N, 1 ≤ Q ≤ 105)
- N-1줄에 걸쳐, U V의 형태로 트리에 속한 간선의 정보가 주어진다. (1 ≤ U, V ≤ N, U ≠ V)
- Q줄에 걸쳐, 문제에 설명한 U가 하나씩 주어진다. (1 ≤ U ≤ N)
출력
- Q줄에 걸쳐 각 쿼리의 답을 정수 하나로 출력
코드
import java.io.*;
import java.util.*;
public class Main {
static int N, R, Q; // 정점의 수, 루트 번호, 쿼리 수
static ArrayList<Integer>[] list; // 그래프 정보
static int[] subSize;
static void dfs(int cur, int prv) {
subSize[cur] = 1;
for (Integer nxt : list[cur]) {
if (nxt == prv) continue;
dfs(nxt, cur);
subSize[cur] += subSize[nxt];
}
}
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st;
st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
R = Integer.parseInt(st.nextToken());
Q = Integer.parseInt(st.nextToken());
list = new ArrayList[N + 1];
for (int i = 0; i < N + 1; i++) {
list[i] = new ArrayList<>();
}
int node1, node2;
for (int i = 0; i < N - 1; i++) {
st = new StringTokenizer(br.readLine());
node1 = Integer.parseInt(st.nextToken());
node2 = Integer.parseInt(st.nextToken());
list[node1].add(node2);
list[node2].add(node1);
}
subSize = new int[N + 1];
dfs(R, 0);
int U;
StringBuilder sb = new StringBuilder();
while (Q-- > 0) {
U = Integer.parseInt(br.readLine());
sb.append(subSize[U] + "\\n");
}
bw.write(String.valueOf(sb));
bw.flush();
bw.close();
br.close();
}
}
알고리즘 문제) BOJ 1967. 트리의 지름
문제 요약
- 트리의 지름 : 트리에 존재하는 모든 경로들 중에서 가장 긴 것의 길이
- 입력으로 루트가 있는 트리를 가중치가 있는 간선들로 줄 때, 트리의 지름을 구해서 출력하는 프로그램을 작성
시간 제한
- 2초
입력
- 첫번째 줄은 노드의 개수 n(1 ≤ n ≤ 10,000)
- 둘째 줄부터 n-1개의 줄에 각 간선에 대한 정보
- 첫 번째 정수는 간선이 연결하는 두 노드 중 부모 노드의 번호를 나타내고, 두 번째 정수는 자식 노드를, 세 번째 정수는 간선의 가중치
- 루트 노드의 번호는 항상 1이라고 가정하며, 간선의 가중치는 100보다 크지 않은 양의 정수
출력
- 첫째 줄에 트리의 지름을 출력
코드
import java.io.*;
import java.util.*;
public class Main {
static int N; // 노드 개수
static ArrayList<Node>[] list; // 그래프 정보
static int max, tmpNode; // 지름 max 값, 트리 지름에 속할 노드 번호
static class Node {
int no;
int weight;
Node(int no, int weight) {
this.no = no;
this.weight = weight;
}
}
static void dfs(int cur, int prv, int w) {
if (max < w) {
max = w;
tmpNode = cur;
}
for (Node nxt : list[cur]) {
if (nxt.no == prv) continue;
dfs(nxt.no, cur, w + nxt.weight);
}
}
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st;
N = Integer.parseInt(br.readLine());
list = new ArrayList[N + 1];
for (int i = 0; i < N + 1; i++) {
list[i] = new ArrayList<>();
}
int node1, node2, weight;
for (int i = 0; i < N - 1; i++) {
st = new StringTokenizer(br.readLine());
node1 = Integer.parseInt(st.nextToken());
node2 = Integer.parseInt(st.nextToken());
weight = Integer.parseInt(st.nextToken());
list[node1].add(new Node(node2, weight));
list[node2].add(new Node(node1, weight));
}
dfs(1, 0, 0);
dfs(tmpNode, 0, 0);
bw.write(String.valueOf(max));
bw.flush();
bw.close();
br.close();
}
}
알고리즘 문제) BOJ 3584. 가장 가까운 공통 조상
문제 요약
- 루트가 있는 트리가 주어지고, 두 노드가 주어질 때 그 두 노드의 가장 가까운 공통 조상을 찾는 프로그램을 작성
시간 제한
- 1초
입력
- 테스트 케이스의 개수 T
- 각 테스트 케이스마다, 첫째 줄에 트리를 구성하는 노드의 수 N이 주어짐
- 2 ≤ N ≤ 10,000
- 그 다음 N-1개의 줄에 트리를 구성하는 간선 정보가 주어짐
- A B
- A가 B의 부모
- A B
- 테스트 케이스의 마지막 줄에 가장 가까운 공통 조상을 구할 두 노드가 주어짐
출력
- 각 테스트 케이스 별로, 첫 줄에 입력에서 주어진 두 노드의 가장 가까운 공통 조상을 출력
접근법
- 카운팅 배열로 풀기
코드
import java.io.*;
import java.util.*;
public class Main {
static ArrayList<Integer>[] list;
static ArrayList<Integer> parent1;
static ArrayList<Integer> parent2;
static int[] counting;
static void dfs(int cur, int prv, ArrayList<Integer> parent) {
for (Integer nxt : list[cur]) {
if (nxt == prv) continue;
parent.add(nxt);
dfs(nxt, cur, parent);
}
}
static int findLCA() {
int answer = parent1.get(parent1.size() - 1);
for (int i = parent1.size() - 1; i >= 0; i--) {
counting[parent1.get(i)]++;
}
for (int i = parent2.size() - 1; i >= 0; i--) {
if (counting[parent2.get(i)] == 0) {
answer = parent2.get(i + 1);
break;
}
}
return answer;
}
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st;
int T = Integer.parseInt(br.readLine());
int N, input1, input2, node1, node2;
StringBuilder sb = new StringBuilder();
while (T-- > 0) {
N = Integer.parseInt(br.readLine());
list = new ArrayList[N + 1];
for (int i = 0; i < N + 1; i++) {
list[i] = new ArrayList<>();
}
for (int i = 0; i < N - 1; i++) {
st = new StringTokenizer(br.readLine());
input1 = Integer.parseInt(st.nextToken());
input2 = Integer.parseInt(st.nextToken());
list[input2].add(input1);
}
st = new StringTokenizer(br.readLine());
node1 = Integer.parseInt(st.nextToken());
node2 = Integer.parseInt(st.nextToken());
parent1 = new ArrayList<>();
parent2 = new ArrayList<>();
parent1.add(node1);
dfs(node1, 0, parent1);
parent2.add(node2);
dfs(node2, 0, parent2);
counting = new int[N + 1];
sb.append(findLCA() + "\\n");
}
/*
2
|
3
| \\
4 1
|
5
* */
bw.write(String.valueOf(sb));
bw.flush();
bw.close();
br.close();
}
}
알고리즘 문제) BOJ 14267. 회사 문화 1
문제 요약
- 상사가 한 직속 부하를 칭찬하면 그 부하의 모든 부하들이 칭찬을 받는다.
- 직속 상사와 직속 부하관계에 대해 주어지고, 칭찬에 대한 정보가 주어질 때, 각자 얼마의 칭찬을 받았는지 출력
시간 제한
- 2초
입력
- 첫째 줄에는 회사의 직원 수 n명, 최초의 칭찬의 횟수 m이 주어진다
- 직원은 1번부터 n번까지 번호가 매겨져 있다. (2 ≤ n, m ≤ 100,000)
- 둘째 줄에는 직원 n명의 직속 상사의 번호가 주어진다
- 직속 상사의 번호는 자신의 번호보다 작으며, 최종적으로 1번이 사장
- 1번의 경우, 상사가 없으므로 -1이 입력
- 다음 m줄에는 직속 상사로부터 칭찬을 받은 직원 번호 i, 칭찬의 수치 w가 주어진다. (2 ≤ i ≤ n, 1 ≤ w ≤ 1,000)
출력
- 1번부터 n번의 직원까지 칭찬을 받은 정도를 출력
접근법
- 특정 루트노드에서 시작하면 해당 노드의 자식 노드까지 칭찬 수치를 받게 됨
- 시간 초과 문제를 해결해야한다.
- 매 쿼리마다 dfs를 돌면 시간초과가뜬다.
코드
import java.io.*;
import java.util.*;
public class Main {
static int N, M; // 노드 개수, 칭찬 횟수
static ArrayList<Integer>[] list;
static int[] check;
static int[] score; // 칭찬 점수
/*
1
|
2
|
3
|
4
|
5
* */
// {0,0,2,4,0,6}
static void dfs(int cur, int prv, int total) {
if (check[cur] > 0) {
total += check[cur];
}
score[cur] += total;
for (Integer nxt : list[cur]) {
if (prv == nxt) continue;
dfs(nxt, cur, total);
}
}
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st;
st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
list = new ArrayList[N + 1];
for (int i = 0; i < N + 1; i++) {
list[i] = new ArrayList<>();
}
st = new StringTokenizer(br.readLine());
int parent;
for (int c = 1; c <= N; c++) {
parent = Integer.parseInt(st.nextToken());
if (parent != -1) list[parent].add(c);
}
score = new int[N + 1];
check = new int[N + 1];
int start, c;
while (M-- > 0) {
st = new StringTokenizer(br.readLine());
start = Integer.parseInt(st.nextToken());
c = Integer.parseInt(st.nextToken());
check[start] += c;
}
dfs(1, 0, 0);
StringBuilder sb = new StringBuilder();
for (int i = 1; i <= N; i++) {
sb.append(score[i] + " ");
}
bw.write(String.valueOf(sb));
bw.flush();
bw.close();
br.close();
}
}
알고리즘 문제) BOJ 26159. 트리와 수열
문제 요약
- N개의 정점이 존재하고, 각 정점은 1번부터 N번까지 번호가 매겨짐
- N-1개의 음이 아닌 정수로 이루어진 수열이 존재
- 간선에 수열의 원소를 하낚씩 대응시켜 가중치를 매기려고 함
- 이때 트리 i번 정점과 j번 정점 사이의 단순 경로 가중치 합이 최소가 되도록 구하기
시간 제한
- 2초
입력
- 정점의 개수 N
- 2≤N≤10만
- N-1개의 줄에 각 간선이 연결하는 두 점이 공백으로 구분하여 주어짐
- 다음 줄에 수열의 원소 N-1개가 주어짐
- 1≤원소≤10억
출력
- i번 정점과 j번 정점 사이의 단순 경로 가중치 합의 최솟값을 1000000007로 나눈 나머지 출력
코드
import java.io.*;
import java.util.*;
public class Main {
static int N;
static ArrayList<Integer>[] list;
static long[] arr;
static long[] subSize;
static final int MOD = 1000000007;
static void dfs(int cur, int prv) {
subSize[cur] = 1;
for (Integer nxt : list[cur]) {
if (nxt == prv) continue;
dfs(nxt, cur);
subSize[cur] += subSize[nxt];
}
}
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st;
N = Integer.parseInt(br.readLine());
list = new ArrayList[N + 1];
for (int i = 0; i < N + 1; i++) {
list[i] = new ArrayList<>();
}
int node1, node2;
for (int i = 0; i < N - 1; i++) {
st = new StringTokenizer(br.readLine());
node1 = Integer.parseInt(st.nextToken());
node2 = Integer.parseInt(st.nextToken());
list[node1].add(node2);
list[node2].add(node1);
}
st = new StringTokenizer(br.readLine());
arr = new long[N - 1];
for (int i = 0; i < N - 1; i++) {
arr[i] = Integer.parseInt(st.nextToken());
}
Arrays.sort(arr);
subSize = new long[N + 1];
dfs(1, 0);
for (int i = 0; i < N + 1; i++) {
subSize[i] = subSize[i] * (N - subSize[i]);
}
Arrays.sort(subSize);
long sum = 0;
for (int i = 0, j = N; i < N - 1 ; i++, j--) {
sum += (arr[i] * subSize[j]) % MOD;
}
/*
1
| \\
2 5
| \\
3 4
3*2 1*4 1*4 1*4
* */
// 여기서 한 번 더 나눠줘야 함
bw.write(String.valueOf(sum % MOD));
bw.flush();
bw.close();
br.close();
}
}
알고리즘 문제) BOJ 24230. 트리 색칠하기
문제 요약
- 노드가 N개인 트리가 존재하고, 1번부터 N번까지 번호가 붙여있다.
- 트리의 루트는 항상 1번 정점이며 맨 처음에는 모든 정점이 하얀색으로 칠해져 있는 상태
- 색은 섞이지 않고 색칠할 때마다 그 색으로 덮어진다
- 하나의 정점에 색칠하면 해당 정점 아래 있는 모든 정점이 같은 색으로 칠해진다
- 트리의 정보와 정점의 색 정보가 주어진다
- 색 정보는 음이 아닌 정수로 주어지며 값이 0인 경우는 항상 하얀색을 의미한다
- 하얀색을 제외한 색만 사용해서 모든 정점을 주어진 색으로 칠하고 싶을 때 최소 몇 번 색을 칠해야 모든 정점을 원하는 색으로 칠할 수 있는지 구해보자
시간 제한
- 1초
입력
- 정점 개수 N
- 1≤N≤20만
- 1번 정점부터 N번 정점까지 각 색 정보 Ci가 구분되어 주어짐
- 0≤Ci≤N
- 셋째 줄부터 N-1개 줄에 걸쳐 연결된 두 정점 a,b가 공백으로 구분되어 주어짐
- 1≤a,b≤N(a≠b)
출력
- 하얀색을 제외한 색만 사용해서 모든 정점을 원하는 색으로 칠하기 위해 최소 몇 번 칠하면 되는지 출력
코드
import java.io.*;
import java.util.*;
public class Main {
static int N;
static ArrayList<Integer>[] list;
static int[] color;
static int answer;
// 0 0 2 0 1 2 2
static void dfs(int cur, int prv, int paint) {
if (paint != color[cur]) answer++;
if (color[cur] > 0){
paint = color[cur];
}
for (Integer nxt : list[cur]) {
if (nxt == prv) continue;
dfs(nxt, cur, paint);
}
}
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st;
N = Integer.parseInt(br.readLine());
list = new ArrayList[N + 1];
for (int i = 0; i < N + 1; i++) {
list[i] = new ArrayList<>();
}
color = new int[N + 1];
st = new StringTokenizer(br.readLine());
for (int i = 1; i <= N; i++) {
color[i] = Integer.parseInt(st.nextToken());
}
int node1, node2;
for (int i = 0; i < N - 1; i++) {
st = new StringTokenizer(br.readLine());
node1 = Integer.parseInt(st.nextToken());
node2 = Integer.parseInt(st.nextToken());
list[node1].add(node2);
list[node2].add(node1);
}
dfs(1, 0, 0);
bw.write(String.valueOf(answer));
bw.flush();
bw.close();
br.close();
}
}