https://programmers.co.kr/learn/courses/30/lessons/43162

  • flow
    간단히 보면 n x n 배열의 원소들을 모두 탐색하는 문제이다. 최적화 해서 몇가지 원소들을 탐색하지 않아도 되게끔 만드려고 해도 결국 O(n^2) 이기 때문에 쉽게 가도록 하겠다.
    키워드가 dfs 와 bfs 인데 둘중 어느 것을 써도 상관 없는 문제이다.
    결국은 dfs든 bfs든 주어진 computers 배열을 가지고 만들어지는 트리의 갯수가 문제의 답이 될 것이다.
    나는 스택이나 큐같은 것을 쓰기 싫어서 그냥 너비 우선 탐색 비슷한 개념으로 단순히 index 순서를 이용해서 코드를 작성했다. 몇가지 자잘한 최적화를 무시해서 그런지 살짝 찝찝하지만 나쁘진 않은 것 같다.

  • result
    https://github.com/songjy6565/alg-py/blob/master/programmers/level3/A3.py