[프로그래머스] 등대 C++ (Lv.3)

 

 

 

 

 

https://school.programmers.co.kr/learn/courses/30/lessons/133500

프로그래머스

 

이번 문제는 dfs 문제였습니다.

 

 

 

 

 

📝 문제 풀이

1. 등대의 연결 정보를 info 벡터에 저장

2. 등대 사이의 뱃길이 n-1개 이므로 트리. 1을 루트 노드로 하여 dfs 수행

• 현재 노드와 연결된 노드가 부모 노드가 아니라면 dfs 수행
• 각 노드의 dfs 수행이 끝난 후, 자식과 부모 등대 모두 불이 꺼져 있다면 부모 등대 불 켜주기 isLightOn[node] = true
• 등대에 불을 켜 줄때마다 answer++

 

 

 

 

👩🏻‍💻 C++ 코드

#include <string>
#include <vector>
#define MAX 100001

using namespace std;

int answer = 0;
bool isLightOn[MAX] = {0}; // 불이 켜진 등대인지 체크

void dfs(int node, int parent, vector<vector<int>> &info) {
    for (int i=0; i<info[node].size(); i++) {
        if (info[node][i] != parent) {
            dfs(info[node][i], node, info);
            
            // 자식과 부모 등대 모두 불이 꺼져 있다면 부모 등대 불 켜주기
            if (!isLightOn[info[node][i]] && !isLightOn[node]) {
                isLightOn[node] = true;
                answer++;
            }
        }
    }
}

int solution(int n, vector<vector<int>> lighthouse) {
    vector<vector<int>> info(n+1);
    
    for (int i=0; i<lighthouse.size(); i++) {
        info[lighthouse[i][0]].push_back(lighthouse[i][1]);
        info[lighthouse[i][1]].push_back(lighthouse[i][0]);
    }
    
    // 트리이기 때문에 1부터 시작
    dfs(1, 1, info);
    
    return answer;
}

 

프로그래머스 - 결과 화면