C++:: 프로그래머스 < 등대 >

접근은 비슷하게 하였으나 코드가 상당히 난잡해지고 메모리 사용 제한에 걸려서 다른 분의 풀이를 참고하였다. 해당 풀이의 핵심적인 부분은 부모에서 자식 노드로 타고 들어가면서 만약 부모 또는 자식 노드의 등대가 불이 안켜졌다면 켜주는 방식의 풀이이다.

#include <string>
#include <vector>
using namespace std;

int answer = 0;
bool isLightOn[100001] = {false, };

void dfs(int node, int parent, vector<vector<int>> &routes) {
    for (int i=0; i<routes[node].size(); i++) {
        if (routes[node][i] != parent) {// 자식에서 부모로 돌아가는 노드가 아니라면
            dfs(routes[node][i], node, routes);// dfs(현재 노드의 자식, 노드, routes)
            if (!isLightOn[routes[node][i]] && !isLightOn[node]) {// 부모 자식 둘다 불이 안켜져있다면
                isLightOn[node] = true;
                answer++;
            }
        }
    }
}

int solution(int n, vector<vector<int>> lighthouse) {
    vector<vector<int>> routes(n+1);
    for(auto num : lighthouse) {
        routes[num[0]].push_back(num[1]);
        routes[num[1]].push_back(num[0]);
    }
    dfs(1, 1, routes);
    return answer;
}