[JS,Python] 등대

시간이 매우매우매우매우 걸렸던 문제였다. (내잘못인가 아닌가..) 먼저 필자가 문제에 접근한 방식은 아래와 같다. 1. 그래프가 최소신장트리 이므로 한점을 부모 노드로 잡고 아래로 내려가는 구조로 바꾸는 것이 가능하다. 2. 이때 자식 노드 중에 더이상 자식이 없는 뿌리노드가 포함되어 있다면 해당 부모 노드는 무조건 불이 켜져있어야 한다. 3. 자식노드 중에 뿌리가 없는 노드가 있다면 해당 노드에 불이 켜져있는 경우와 꺼져있는 경우를 비교해줘야 한다. - 이 경우 dfs탐색을 통해서 하다보면 검사한 노드를 또 검사하는 일이 계속 생기게 된다. 4. 따라서 2차원 dp[n][2] 만큼을 생성해서 노드 n이 켜져있는지 꺼져있는데 2가지 경우를 담아서 계산을 한다. - 예를 들어서 3번 노드에 불이 켜져있는지..