본문 바로가기

트리

(15)
[백준 / BOJ] 11780 플로이드 2 (Java) 문제 출처 : https://www.acmicpc.net/problem/11780 11780번: 플로이드 2 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 www.acmicpc.net n개의 도시와 n개의 도시를 연결하는 m개의 버스가 있을때, 각 도시를 오가기위해 지불해야하는 버스의 최소비용과 이때의 경로를 구하는 문제다. 풀이 푸는데 2일이나 걸린 문제다.. 경로를 찾는과정에서 생각보다 어려움을 겪었는데, Java언어가 String을 이어붙이는 메커니즘상(Java는 String을 붙일경우 새로운 String객체를 생성한다.) 각 경로를 비교해가며 최단경로를..
[백준 / BOJ] 20955 민서의 응급 수술 문제 출처 : https://www.acmicpc.net/problem/20955 20955번: 민서의 응급 수술 민서는 강원대학교 컴퓨터공학과의 신임 교수이다. 그녀가 저술한 효율적인 택배 배달을 위한 최적 경로 설계에 관한 연구 논문은 아직도 널리 인용되고 있다. 오늘도 열심히 강의를 하던 민서 www.acmicpc.net N개의 뉴런(노드) 와 M개의 시냅스(간선)가 주어진다. 이때, M개의 시냅스를 적절히 끊거나 연결해서 N개의 뉴런을 하나의 '트리'구조로 만들려고한다. 끊거나 연결하는 연산횟수를 구하는 문제다. 풀이 트리의 정의인 '트리는 항상 N-1개의 간선으로 연결된다'를 이용하면 쉽게 풀리는 문제다. 문제 입력의 노드가 항상 전부 연결된상태로 주어지는것이 아니기 때문에, 우선 연결된 그래프..
[백준 / BOJ] 23040 누텔라 트리 (Easy) 문제 출처 : https://www.acmicpc.net/problem/23040 23040번: 누텔라 트리 (Easy) 첫째 줄에 트리의 정점의 개수 $N$이 주어진다. ($2 \le N \le 100\,000$) 이후 $(N-1)$개 줄에 걸쳐 각 간선이 잇는 두 정점의 번호 $u_i$, $v_i$가 공백을 사이에 두고 주어진다. ($1 \le u_i \le N$, $1 \le v_i \le N$, www.acmicpc.net 빨간색과 검은색 정점들로 이루어진 트리가 있다. 시작은 검은색 정점, 나머지 정점은 모두 빨간색인 경우 이를 누텔라 경로라고한다. 트리에서 누텔라 경로의 갯수를 찾는 문제였다. 풀이 시간초과를 주의해야했던 문제였다. 논리는 아래와 같다. 검은색 정점에서 시작해, 거쳐간 빨간색 ..
[백준 / BOJ] 23089 사탕나무 문제 출처 : https://www.acmicpc.net/problem/23089 23089번: 사탕나무 기준이 되는 사탕을 3번 사탕으로 정하면 총 5개의 사탕을 먹을 수 있다. www.acmicpc.net 트리구조의 사탕나무에 사탕이 열려있다. 안즈는 기준이 되는 사탕하나를 골라 해당 사탕부터 K이하에 있는 모든 사탕을 먹을려한다. 이때, 최대로 먹을 수 있는 사탕의 갯수를 출력하는 프로그램을 만드는 문제다. 풀이 누적 합에 DP를 이용해 푼 문제다. 문제 풀이 자체는 어렵지 않았으나, 구현시 신경써야할점이 많았었다. 구현 문제에서 어려웠던것은, K가 1초과일때(K가 1초과인 이유는 K가 1이라면, 자신의 자식만 확인하면되므로 문제되지 않기 때문이다.), K번째 자식까지 선택한 사탕의 갯수를 빠르게 ..
[백준 / BOJ] 2533 사회망 서비스(SNS) 문제 출처 : https://www.acmicpc.net/problem/2533 2533번: 사회망 서비스(SNS) 페이스북, 트위터, 카카오톡과 같은 사회망 서비스(SNS)가 널리 사용됨에 따라, 사회망을 통하여 사람들이 어떻게 새로운 아이디어를 받아들이게 되는가를 이해하는 문제가 중요해졌다. 사회망 www.acmicpc.net N명의 친구들이 서로 트리 형태로 연결되어있다. 친구들은 자신의 친구들이 모두 얼리어답터 일때, 자신도 얼리어답터가 된다. 이때, 모든 친구를 얼리어답터를 만들기위해 필요한 초기 얼리어답터 수를 구하는 문제다. 풀이 다이나믹 프로그래밍으로 푼 문제다. 트리에서의 DP의 전형적인? 유형으로 DP로 풀리는것을 떠올리는것이 문제였다. 아이디어 트리의 현재 노드에 할수있는 연산은 두 ..
[백준 / BOJ] 19542 전단지 돌리기 문제 출처 : https://www.acmicpc.net/problem/19542 19542번: 전단지 돌리기 현민이는 트리 모양의 길 위에서 오토바이를 타고 전단지를 돌리려고 한다. 현민이의 목표는 케니소프트에서 출발하여 모든 노드에 전단지를 돌리고, 다시 케니소프트로 돌아오는 것이다. 현민 www.acmicpc.net 현민이는 트리 모양의 길 위에서 오토바이를 타고 전단지를 돌리려고 한다. 현민이는 KENNYSOFT위치에서 시작하여 전단지를 다 돌리고 KENNYSOFT로 돌아오며, 이때, 전단지를 던져 거리가 D미만인 노드에 전단지를 한번에 돌릴 수 있다. 현민이가 전단지를 모든 노드에 돌리고 KENNYSOFT로 돌아오는 최단 경로를 구하는 문제다. 풀이 트리탐색으로 풀리는 문제였다. 1년전에 풀려고..
[백준 / BOJ] 15900 나무 탈출 문제 출처 : https://www.acmicpc.net/problem/15900 15900번: 나무 탈출 평소에 사이가 좋지 않던 성원이와 형석이가 드디어 제대로 한 판 붙으려고 한다. 성원이와 형석이 둘과 모두 똑같이 친한 인섭이가 대결 종목을 정해 가져왔다. 바로 '나무 탈출' 이라는 보드게 www.acmicpc.net 트리의 정점의 개수 N, N-1개의 줄에 거쳐 간선의 정보가 주어진다. 각 간선의 끝(리프노드)에 게임 말이 존재한다. 성원이와 형석이는 이 게임 말을 한턴에 한번씩 부모노드로 움직이는 방식으로 게임을 진행하려고한다. 게임 말은 루트노드에 도착하면 사라지며, 이 과정을 반복하다 자신의 턴에 더 이상 고를수있는 게임 말이 없다면, 그 사람은 게임에서 패배한다. 항상 성원이가 먼저 시작..
[백준 / BOJ] 1240 노드사이의 거리 문제 출처 : https://www.acmicpc.net/problem/1240 1240번: 노드사이의 거리 N(2≤N≤1,000)개의 노드로 이루어진 트리가 주어지고 M(M≤1,000)개의 두 노드 쌍을 입력받을 때 두 노드 사이의 거리를 출력하라. www.acmicpc.net N개의 노드로 이루어진 트리가 주어지고, M개의 쿼리가 주어질때, 노드 사이의 거리를 구하는 프로그램을 만드는 문제다. 풀이 트리 + 완전탐색 문제다. N이 1000, M이 1000으로, 한번탐색할때마다 최대 1000번 반복한다고 가정했을때, 최악의경우, 1000*1000번 반복하므로 시간복잡도는 O(NM)이 된다. 트리구조를 만든다음에 A위치에서 시작했을때, B위치에 도달했을때의 거리를 구하면된다. 거리구하는 소스코드 priv..