문제https://www.acmicpc.net/problem/14267 풀이트리에서의 dfs 방법으로 문제를 해결했습니다. dfs이지만, 배열에서의 누적 합의 매커니즘과 굉장히 비슷한 문제입니다. 누적합은 쉽게 말해, [0,1,1,0,1,1] 과 같은 배열을 nums[i+1] += nums[i] 와 같은 식을 통해 [0,1,2,2,3,4] 과 같은 결과를 도출하는 것입니다. 이 문제도 마찬가지로, 배열에 값을 입력받고 누적합을 돌리는데 위와 같이 인덱스가 연속된 경우가 아닙니다. 그래서 연속된 인덱스를 dfs로 탐색하며 누적합을 시키는 매커니즘입니다. 값을 입력받을 때, list에 사원 번호를 연결시킵니다. 그리고 1번(사장)에서 dfs를 시작해, score 배열을 누적 합을 시켜나갔습..
DFS
문제https://www.acmicpc.net/problem/15681 풀이 서브 트리에 속한 정점의 개수를 세는 문제입니다. dfs를 통해 그래프를 탐색하며, 서브 트리의 루트가 인덱스인 배열에 정점의 개수를 저장합니다. 처음에 문제를 풀이할 때, 루트가 아닌 제일 마지막 자식부터 dfs 탐색을 시작해보려고도 했지만, 그렇게 접근하면 마지막 자식도 체크해야하고, 방문 배열을 통해 접근을 막아주어야하고.. 여러모로 로직이 복잡해집니다. 그래서 루트부터 출발해 자식으로 뻗어가며 subtrees 배열에 정점의 개수를 저장합니다. 이때 부모 노드에 자식 노드가 가진 정점의 개수를 더해주면 됩니다. 주의할 것은, 부모에서 자식으로 내려갔는데 다시 부모 노드를 검사하지 않도록 하는 것입니다. 이것은 d..
문제https://www.acmicpc.net/problem/1240 풀이 트리에서의 탐색 문제입니다. Dfs를 이용해서 문제를 해결했습니다. 우선 Arraylist[] 배열에 입력값을 입력받습니다. 이 때, 방향은 양방향 모두 갈 수 있으니 양뱡향으로 입력 받습니다. 그리고 dfs메서드를 통해 시작점부터 탐색을 시작합니다. 한 가지 주의해야할 것은, 거리의 합을 구하는 것에 있습니다. 만약 아래와 같은 입력 값이 주어질 때를 생각해보겠습니다. 4 11 2 12 3 12 4 11 4// 정답 2 이 반례 코드에서 2는 3, 4의 두 방향으로 뻗게 됩니다. 그래서 3으로 보낸 dfs에서 거리의 합에 거리를 더하고, 그것을 바로 4로 보내게 되면 중복해서 값이 들어가게 됩니다. 그래서 한 노드에서 ..
