[LeetCode][py] 1519. Number of Nodes in the Sub-Tree With the Same Label

Table of Contents

• 문제
• 예제
• 계획
• 풀이

문제

원문 보기 : [LeetCode] 1519. Number of Nodes in the Sub-Tree With the Same Label

0부터 n-1까지 번호가 매겨진 n개의 노드와 정확히 n-1개의 간선(edges)을 갖는 트리(연결되어 있고 무방향이지만 사이클이 없는 그래프)가 주어진다. 루트는 0번 노드이고, 각 노드는 영어 소문자 라벨을 갖는다. 라벨은 문자열 labels에 있고, i번 노드의 라벨은 labels[i]이다.

간선 배열은 edges[i] = [a_i, b_i]의 형태로 주어지며, a_i와 b_i 사이에 간선이 존재한다는 의미이다.

크기가 n이고 ans[i]는 노드 i와 그 하위 트리에 있는 노드 중 동일한 레이블을 가진 것의 수인 배열을 반환하라.

조건(Constraints):

• 1 <= n <= 105
• edges.length == n - 1
• edges[i].length == 2
• 0 <= ai, bi < n
• ai != bi
• labels.length == n
• labels는 영어 소문자만을 갖는다.

예제

* 그림은 원문 참고

Example 1:

Input: n = 7, edges = [[0,1],[0,2],[1,4],[1,5],[2,3],[2,6]], labels = "abaedcd"
Output: [2,1,1,1,1,1,1]
Explanation: Node 0 has label 'a' and its sub-tree has node 2 with label 'a' as well, thus the answer is 2. Notice that any node is part of its sub-tree.
Node 1 has a label 'b'. The sub-tree of node 1 contains nodes 1,4 and 5, as nodes 4 and 5 have different labels than node 1, the answer is just 1 (the node itself).

Example 2:

Input: n = 4, edges = [[0,1],[1,2],[0,3]], labels = "bbbb"
Output: [4,2,1,1]
Explanation: The sub-tree of node 2 contains only node 2, so the answer is 1.
The sub-tree of node 3 contains only node 3, so the answer is 1.
The sub-tree of node 1 contains nodes 1 and 2, both have label 'b', thus the answer is 2.
The sub-tree of node 0 contains nodes 0, 1, 2 and 3, all with label 'b', thus the answer is 4.

Example 3:

Input: n = 5, edges = [[0,1],[0,2],[1,3],[0,4]], labels = "aabab"
Output: [3,2,1,1,1]

계획

1. 상황 파악
   • 라벨의 개수를 세려면 트리를 돌아다녀야 한다. 트리 순회!
   • 무방향 그래프지만 서브트리에 대해서만 순회해야 하므로 방향 그래프처럼 생각해야 한다.
2. DFS vs BFS
   DFS는 무방향 그래프를 방향 그래프처럼 취급하면서, 순회하고 개수를 세는 데에는 잘 맞지 않는다. 잘 쓰면 물론 답은 나오겠지만 그 잘 쓰는 게 참 번거로울 것이 예상된다. BFS를 쓰는 게 적절하다.
3. 계획
   문제에서 주어지는 간선은 방향이 없기 때문에 노드 번호를 이용해 작은 번호에서 큰 번호로 가는 방향만 이용해야 한다. 현재 검사하고 있는 서브트리보다 위로 올라가면 안 되니까.
4. 더 자세한 계획
5. 답안으로 반환할 배열은 크기가 정해져 있으니 처음부터 0으로 채워서 만들어 둔다.
6. 노드의 개수만큼 겉 반복문을 쓴다.
7. 겉 반복문 안에서 안쪽 반복문으로 BFS를 돈다. 이때 현재 서브트리 루트의 라벨을 저장해 뒀다가 같은 라벨이 나오면 개수를 세어야 한다.
   BFS는 큐를 이용하고, 큐에 추가하는 간선은 무조건 서브트리 루트에서 리프로 향하는 방향만 취급한다.
8. 사용 언어 : 요즘 노트북이 다른 일로 바빠서 비주얼 스튜디오까지 켜고 싶지는 않으니 파이썬이다. 그리고 cpp 쓰면 전에 쓴 코드 베낄 거잖아. 직접 머리를 쓰자고요.
9. BFS 정리 좀 해보자
   1. 큐와 방문 여부 배열을 준비한다. 큐는 비어있고, 방문 여부 배열은 노드의 수만큼 false로 채워져 있다.
   2. 시작점에서 나가는 모든 간선을 큐에 추가해둔다.
   3. 이후 큐가 빌 때까지 반복한다
      • 큐에서 간선을 하나 꺼낸다
      • 간선이 향하는 곳이 이미 방문한 곳인지 확인하고, 방문했다면 다음 반복으로 continue
      • 간선이 도착한 곳을 방문한 곳으로 표시한다
      • 도착한 곳에서 나가는 모든 간선을 큐에 추가한다.
10. 틀렸다. 편의를 위해서도 있고, 예제는 모두 루트에서 리프로 노드 번호가 커지게 쓰여 있어서 노드 번호도 어느 정도 정렬된 상태로 주는 걸 전제로 코드를 썼는데 딱 그 부분에서 반례가 발견됐다. 문제 어디에도 노드 번호를 순서대로 준다는 말은 없었으니 내가 틀린 거다. 어떻게 고쳐야 하나?
    번호가 큰 노드에서 작은 노드로 갈 때, 이 방향이 리프로 가는 방향이라는 걸 어떻게 알 수 있지?

풀이

답은 말고 풀이를 봤다. 어쩐지 DFS 풀이가 더 많다 싶었는데, 내가 반대로 생각해서 어려운 거였다. 루트에서 리프로 가면서 개수를 세는 게 아니라 리프에서 루트로 올라오면서 개수를 세어서 합치는 거랬다.

이 풀이를 잊어버린 후에 다시 풀겠다고 하고 싶지만 사실 나는 내가 이 문제를 다시 들여다 볼 가능성이 낮다는 걸 알고 있어요. 그럼에도 묵혀두겠습니다. 다른 게 더 하고싶어.