트리10 [백준] 19542: 전단지 돌리기 - JAVA https://www.acmicpc.net/problem/19542 풀이트리모양의 길 위에서 전단지를 돌리는데, 현재 노드에서 거리가 d이하인 노드들에는 현재 노드에서 전단지를 돌릴 수 있다. 따라서, 어떤 노드로부터 리프 노드까지의 거리가 d이하라면 더이상 앞으로 나아가지 않아도 된다는 것이다. dfs탐색을 통해 리프까지의 최대 거리를 구한다. 해당 거리가 d이상이라면 `cnt`값을 늘려줬다. 다시 시작 정점으로 돌아와야 하므로 `cnt * 2`가 정답이 된다. 메모리: 70564KB시간: 456ms언어: Java 11import java.io.*;import java.util.*;public class Main { static int s, d, cnt; static ArrayList> g.. 2024. 7. 13. [백준] 14267: 회사 문화 1 - JAVA https://www.acmicpc.net/problem/14267 풀이상사가 직속 부하를 칭찬할 수 있는데 a가 b에게 10의 칭찬을 했다면 b의 직속 부하인 c도 10의 칭찬을 받는 것이 된다. 각 번호의 직원마다 직속 상사의 번호가 주어져 저장했다. 직속 상사로부터 칭찬을 받은 직원의 번호와 칭찬 수치가 주어지는데, int배열을 만들어 저장했다. 1번이 사장이므로 1번부터 시작하여 트리를 타고 내려가면서 int배열의 값을 부모 노드에서 자식 노드에 더해주는 식으로 구현했다. 메모리: 76068KB시간: 792ms언어: Java 11import java.io.*;import java.util.*;public class Main { static ArrayList> list; static i.. 2024. 5. 19. [프로그래머스] 양과 늑대 - JAVA https://school.programmers.co.kr/learn/courses/30/lessons/92343 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 풀이늑대의 수가 양의 수 이상이 되면 양들이 다 잡아먹혀서 안된다. 트리의 0번부터 시작해서 양을 늑대보다 많게 하면서 돌아다닌다. 이때 양의 최댓값을 찾아야한다. 이동이 가능한 노드들을 담는 리스트를 만들었다. 특정 노드를 방문 할 때 그 노드의 자식 노드를 리스트에 담고, 해당 노드는 제거해주었다. 이동가능한 리스트를 들고 dfs탐색을 통해 최댓값을 갱신했다. 리스트에서 노드를 제거할 때 Conc.. 2024. 5. 18. [백준] 2250: 트리의 높이와 너비 - JAVA https://www.acmicpc.net/problem/2250 풀이트리를 격자모양의 틀에 넣을 때 트리의 깊이별로 너비를 구했을 때 최댓값을 찾는 문제. 입력받으면서 트리를 저장하는데, 부모, 왼쪽 자식, 오른쪽 자식을 저장한다. 입력받아서 저장한 후 부모가 -1로 되있는 것이 루트 노드이다. 루트노드부터 중위순회(왼쪽 - 루트 - 오른쪽)하여 탐색하면 열 번호를 1부터 순서대로 부여할 수 있다. 중위순회할 때 트리의 깊이(level)도 함께 넘겨 각 깊이별로 열 번호의 최대와 최소를 저장한다. 중위순회를 마친 후 깊이별로 너비의 최댓값을 구한다. 메모리: 21176KB시간: 256ms언어: Java 11import java.io.*;import java.util.*;public class Main.. 2024. 5. 14. [백준] 13325: 이진 트리 - JAVA https://www.acmicpc.net/problem/13325 풀이포화이진트리의 에지들에 가중치가 있을 때, 에지들의 가중치를 증가하여 루트에서 리프까지의 거리가 같게 만들어야 한다. 트리의 높이 k 가 주어지는데 이때 트리의 사이즈는 Math.pow(2, k + 1) - 1 이다. 사이즈만큼 배열을 만들어 arr[2]부터 채운다. arr[1]은 루트노드로 값은 0이다. 문제에서는 에지에 가중치가 있다고 표현하고있지만 각 노드들에 가중치를 넣었다. 배열을 채운 후, 루트노드 1 부터 시작하여 dfs탐색을 통해 값을 더한다. 왼쪽 자식 노드와 오른쪽 자식 노드의 값 중 큰 값을 현재 노드의 값에 더해 부모 노드로 반환하고, 답을 저장하는 변수에 현재 노드의 값과 왼쪽 자식, 오른쪽 자식의 차를 더한다.. 2024. 5. 14. [백준] 15681: 트리와 쿼리 - JAVA https://www.acmicpc.net/problem/15681 풀이트리에 속한 간선의 정보가 주어지고, 루트의 번호가 주어진다. 트리의 정점을 포함해 자신보다 하위에 있는 정점들의 개수를 구하는 문제이다. 먼저 간선의 정보를 인접리스트에 담았다. 루트의 번호부터 dfs탐색을 통해 진행하는데 정점의 개수의 최대값이 크다보니 매번 구하면 시간 초과가 발생할 것 같았다. dp배열을 만들어 dfs탐색을 하며 dp에 저장하고 반환하는 식으로 구현했다. 메모리: 77800KB시간: 812ms 언어: Java 11import java.io.*;import java.util.*;public class Main { static ArrayList> tree; static int[] dp; stati.. 2024. 5. 13. [백준] 24230: 트리 색칠하기 - JAVA https://www.acmicpc.net/problem/24230 풀이트리가 주어지고 트리를 주어진 색으로 칠해야 한다. 한 정점에 색을 칠하면 그 정점의 하위 정점들 모두에게 같은 색을 칠한다. 따라서 루트인 1번 정점부터 시작하여 아래로 내려가면서 색이 다르면 색을 칠해줬다. dfs탐색을 통해 먼저 자식의 부모의 색을 따라서 칠하고 원하는 색과 비교하여 색을 다시 칠했다. 메모리: 111952KB시간: 1684ms언어: Java 11import java.io.*;import java.util.*;public class Main { static int N, ans; static int[] arr, color; static ArrayList> list; static boolean.. 2024. 5. 13. [백준] 1991: 트리 순회 - JAVA https://www.acmicpc.net/problem/1991 풀이트리, 재귀. 이진 트리가 주어지고 전위순회, 중위순회, 후위순회한 결과를 출력하면 되는 문제이다. 이진 트리는 각 노드와 왼쪽 자식 노드, 오른쪽 자식노드로 주어져 트리를 구현하여 저장해야 했다. 메모리: 14188KB시간: 124ms언어: Java 11import java.io.*;import java.util.*;public class Main { static StringBuilder sb = new StringBuilder(); static class Node { char ch; Node left; Node right; public Node(char ch) { .. 2024. 5. 12. [백준] 21738: 얼음깨기 펭귄 - JAVA https://www.acmicpc.net/problem/21738 풀이그래프 탐색 문제. 펭귄이 얼음 위에 올라가있는데 떨어지지 않으려면 연결된 지지대 얼음 2개가 필요하다. 최소한의 얼음만 남기고 얼음을 깨야한다. 펭귄의 위치로부터 탐색한다. 먼저 발견한 얼음이 가깝다는 것이므로 먼저 발견한 2개의 지지대 얼음을 제외한 나머지 얼음은 깨는 것으로 한다. 메모리: 152136KB시간: 696ms언어: Java 11import java.io.*;import java.util.*;public class Main { static int N, S, P, ans; static ArrayList> list; public static void main(String[] args) throws IOE.. 2024. 5. 11. [백준] 4256: 트리 - JAVA https://www.acmicpc.net/problem/4256 풀이트리구조의 개념과 재귀를 물어보는 문제였다. 트리의 전위순회, 중위순회한 결과를 알려주고 후위순회한 결과를 찾아야한다. 전위순회: root -> left -> right 중위순회: left -> root -> right 후위순회: left -> right -> root 전위순회에서 맨 앞의 값이 후위순회에서의 맨 마지막 값이 된다. 전위순회의 맨 앞의 값을 중위순회에서 찾아 left그룹과 right그룹으로 나눠 재귀 탐색을 한다. 메모리: 157856KB시간: 644ms언어: Java 11import java.io.*;import java.util.*;public class Main { public static void main.. 2024. 5. 11. 이전 1 다음