1068번: 트리

문제 접근 🤔

• 삭제해야 하는 부모 트리의 인덱스와 입력된 트리 리스트를 입력 값으로 받는 DFS 함수를 선언한다.
• 전달 받은 인덱스의 리스트 값을 삭제한다는 의미로 해당 값을 None 으로 바꾼다.
• 리스트 전체를 탐색하며, 방금 삭제한 인덱스를 부모 노드로 가지는 노드를 찾아 dfs 함수를 재귀 호출한다.
• 재귀가 끝나면 삭제된 노드들은 전부 None 으로 갱신되어 있으므로, 값이 None 이 아니면서, 다른 노드의 부모 노드도 아닌 원소를 찾을 때마다 cnt를 1씩 늘린다.
  
  
  

놓쳤던 부분 😅

• DFS / BFS 를 사용할 때에 가장 중요한 것은 탐색의 기준을 잡는 것이라고 생각한다.
• 이번에는 바로 떠오르지 않아서 다른 분의 답안을 참고 했는데, 삭제해야 하는 인덱스를 기준으로 하고 탐색을 돌리면 생각보다 단순한 문제였다.
• 다양한 문제들을 접하며 문제를 해결할 아이디어를 떠올리는 능력을 더 길러야겠다.
  
  
  

코드 😁

파이썬 코드(40 ms)

n, parentList, k = int(input()), list(map(int, input().split())), int(input())
cnt = 0

def dfs(num, list):
    list[num] = None
    for i in range(len(list)):
        if num == list[i]:
            dfs(i, list)

dfs(k, parentList)

for i in range(len(parentList)):
    if parentList[i] != None and i not in parentList:
        cnt += 1
print(cnt)

자바스크립트 코드(132 ms)

const fs = require('fs');
const filePath = process.platform === 'linux' ? '/dev/stdin' : __dirname + '/input.txt';
const [L, data, K] = fs.readFileSync(filePath).toString().trim().split('\n');

const dfs = (cutNum, list) => {
  list[cutNum] = null;

  for (let i = 0; i < list.length; i++) {
    if (cutNum === list[i]) {
      dfs(i, list);
    }
  }
};

const solution = (parentList, k) => {
  let cnt = 0;
  dfs(k, parentList);

  for (let i = 0; i < parentList.length; i++) {
    if (parentList[i] != null && !parentList.includes(i)) {
      cnt++;
    }
  }
  console.log(cnt);
};

solution(data.split(' ').map(Number), Number(K));