목록트리 (3)

AtraFelis's Develop Diary

[프로그래머스 | JAVA] 전력망을 둘로 나누기 (완전 탐색, BFS)

keyword : 그래프, 트리, 완전탐색, BFS, DFShttps://school.programmers.co.kr/learn/courses/30/lessons/86971  프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 문제n개의 송전탑이 전선을 통해 하나의 트리 형태로 연결되어 있습니다. 당신은 이 전선들 중 하나를 끊어서 현재의 전력망 네트워크를 2개로 분할하려고 합니다. 이때, 두 전력망이 갖게 되는 송전탑의 개수를 최대한 비슷하게 맞추고자 합니다.송전탑의 개수 n, 그리고 전선 정보 wires가 매개변수로 주어집니다. 전선들 중 하나를 끊어서 송전탑 개수가 가능한 비슷하도록 두 전력망으로 나누..
Algorithm/프로그래머스 2025. 2. 27. 00:21
[프로그래머스 | JAVA] 길 찾기 게임 (이진 트리, 순회)

keyword : 트리, 후위 순회, 전위 순회https://school.programmers.co.kr/learn/courses/30/lessons/42892 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 풀이문제 설명은 장황하지만, 요구하는 바는 간단하게 축약된다.직접 이진 트리를 구현할 수 있는가?이진 트리의 순회 방법(전위 순회, 후위 순회)에 대해 아는가?이 두 가지다.맨 처음에는 배열을 이용해 이진 트리를 구현하려 했으나, 정렬한 배열의 인덱스를 맞추는 것이 쉽지 않았고, 때문에 클래스를 선언해서 노드를 저장하는 것이 더 간단하겠다고 판단했다.노드 번호, x, y 좌표, 자식 노드를 저장할 ..
Algorithm/프로그래머스 2025. 2. 26. 02:01
[백준] 11725 - 트리의 부모 찾기 (JAVA)

SILVER II문제루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오.입력첫째 줄에 노드의 개수 N (2 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N-1개의 줄에 트리 상에서 연결된 두 정점이 주어진다.출력첫째 줄부터 N-1개의 줄에 각 노드의 부모 노드 번호를 2번 노드부터 순서대로 출력한다.풀이난이도 보고 쉽게 풀 수 있겠거니 했다가, 통수에 통수를 맞은 문제였다.일단 문제의 풀이 방향은 이렇다.주어지는 입력값을 그래프로 만든다.1번 노드부터(1번은 무조건 root이므로) 차례대로 그래프를 탐색한다. BFS든 DFS든 상관없으나 나는 BFS를 사용하였다.1번 노드와 연결된 노드는 무조건 1번 노드를 부모로 갖는다.이미 부모..
Algorithm/백준 2024. 5. 5. 15:23
이전 Prev 1 Next 다음