[JS,Python] 등대

시간이 매우매우매우매우 걸렸던 문제였다. (내잘못인가 아닌가..)

 

 

먼저 필자가 문제에 접근한 방식은 아래와 같다.

 

1. 그래프가 최소신장트리 이므로 한점을 부모 노드로 잡고 아래로 내려가는 구조로 바꾸는 것이 가능하다.

2. 이때 자식 노드 중에 더이상 자식이 없는 뿌리노드가 포함되어 있다면 해당 부모 노드는 무조건 불이 켜져있어야 한다.

3. 자식노드 중에 뿌리가 없는 노드가 있다면 해당 노드에 불이 켜져있는 경우와 꺼져있는 경우를 비교해줘야 한다.

    - 이 경우 dfs탐색을 통해서 하다보면 검사한 노드를 또 검사하는 일이 계속 생기게 된다.

4. 따라서 2차원 dp[n][2] 만큼을 생성해서 노드 n이 켜져있는지 꺼져있는데 2가지 경우를 담아서 계산을 한다.

    - 예를 들어서 3번 노드에 불이 켜져있는지 검사했다면 dp[3][1]을 조회해서 알 수 있다. 만약 dp[3][1] 이 0 이라면 한번도 조사를 안한 곳이므로 조사를 하면 된다.

5. 어차피 어느 곳을 최상위 부모 노드로 잡든 상관이 없기때문에 1번노드의 등대를 켜진것과 꺼진것을 구분하여 계산한다.

 

 

function solution(n, lighthouse) {
  const graph = [...new Array(n + 1)].map((_, idx) => []);

  for (const [a, b] of lighthouse) {
    graph[a].push(b);
    graph[b].push(a);
  }

  const dp = [...Array(n + 1)].map((_) => [0, 0]);
  const dfs = (curNode, parentNode, check) => {
    let ret = check ? 1 : 0;
    for (const node of graph[curNode]) {
      if (node === parentNode) continue;
      const on = dp[node][0] ? dp[node][0] : dfs(node, curNode, true);
      if (!dp[node][0]) dp[node][0] = on;

      const off = dp[node][1] ? dp[node][1] : dfs(node, curNode, false);
      if (!dp[node][1]) dp[node][1] = off;

      ret += check ? Math.min(on, off) : on;
    }
    return ret;
  };

  return Math.min(dfs(1, 0, true), dfs(1, 0, false));
}

 

 

즉 위처럼 dfs와 dp를 적절히 조합하여 만들었다.

 

그런데

 

테스트 9번 케이스만 '런타임 에러'가 나와 통과되지 않았다...

 

뭔가 느낌적으로 재귀의 깊이 문제인것 같았다.

(파이썬과 JS는 타 언어에 비해서 기본적으로 에러를 뱉는 재귀의 깊이가 매우 낮다)

 

근데 또 문제는 JS는 브라우저 환경에서는 브라우저 엔진이 재귀호출의 깊이를 정하기 때문에 이를 임의대로 바꾸는게 힘들었다. 물론 내가 잘못한 것일 수 있으니..

 

내가 짠 로직을 그대로 파이썬으로 바꿔보았다.

 

def solution(n, lighthouse):
    graph = [[] for _ in range(n+1)]
    
    for a,b in lighthouse:
        graph[a].append(b)
        graph[b].append(a)
        
    dp = [[0,0] for _ in range(n+1) ]
    
    def dfs(curNode,parentNode,check):
        ret = 1 if check else 0
        
        for node in graph[curNode]:
            if node== parentNode: continue
            on = dp[node][0] if dp[node][0] else dfs(node,curNode,True)
            if not dp[node][0]: 
                dp[node][0] = on
            
            off = dp[node][1] if dp[node][1] else dfs(node,curNode,False)
            if not dp[node][1] : 
                dp[node][1] = off
        
            if check:
                ret += min(on,off)
            else:
                ret += on
        return ret
    
    return min(dfs(1,0,True),dfs(1,0,False))
    return graph

 

 

 

파이썬도 통과못하는걸 보니 아마 맞는거 같다.

 

import sys
sys.setrecursionlimit(10**6)

 

다행히 파이썬은 재귀 깊이를 늘릴 수 있다.

 

이렇게 재귀를 늘려보니!! 통과되었다.

 

 

 

 

뭔가 이런 방식 뿐 아니라 다른 방식도 있을 거 같아서 다른 분들의 풀이를 조금 찾아봤다.

 

놀랍게도 그리디를 활용해서 푸는 방법이 있었다.

 

내 코드가 아니기에 여기에 코드를 적진 않고, 풀이방법 유형만 적어보자면

 

 

1. 간선이 1개인 노드는 무조건 등대 불이 꺼져있다.

2. 간선이 1개인 노드와 연결된 노드는 등대 불이 켜져있어야 한다.

3. 1->2 번을 진행한 후에 간선이 1개인 길을 없애준다.

4. 그러면 또다시 간선이 1개인 노드들이 나온다.

5 .간선이 모두사라질때까지 위 과정을 반복하면 답이 나온다!

 

 

 

확실히 그리디로 해결하니까 시간도 더 빨리나오고 메모리 오류도 안나는 좋은 방법이 있었다..