[프로그래머스/C++] 등대

미숙한 블로그 주인이 코딩테스트 문제를 풀어가는 과정을 담은 글입니다. 이 풀이가 효율적인 풀이가 아닐 수 있으며, 부정확한 정보가 많이 있을 수 있습니다. 보완해야할 점이 있다면 댓글로 남겨주세요!

 

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

프로그래머스

등대

풀이

(안전을 위해서라면 그냥 등대 다 켜주면 안 되나?)

 

자신의 불이 꺼져있을 때, 연결된 뱃길 중 하나라도 등대가 꺼져있으면 배가 위험하므로 등대를 하나 켜주자고 한다.

그렇다면 간단히 생각해볼 수 있다. 각 등대를 탐색해서 자신과 연결된 노드 중 하나라도 등대가 꺼져 있다면 자신의 불을 켜면 되는 것이 아닌가!

 

단, 리프 노드의 경우에는 해당되지 않는다는 점을 유의해야 한다. 그렇기 때문에, DFS를 이용해서 리프 노드를 찾은 다음, 등대를 켤지 말지 결정하자!

 

#include <string>
#include <vector>

using namespace std;

void dfs(int node, vector<vector<int>>& ST, vector<bool>& light_on, int& answer, vector<bool>& visited) {
    visited[node] = true;
    bool is_on = false;
    for (int i = 0; i < ST[node].size(); i++) {
        int child = ST[node][i];

        if (visited[child])
            continue;
        
        dfs(child, ST, light_on, answer, visited);
        
        // 자신과 연결된 등대들 중에서 꺼진 곳이 있다면 자신이 등대를 켜줌.
        if (!light_on[child]) {
            if (!is_on) {
                light_on[node] = true;
                answer++;
                is_on = true;
            }
        }
    }
}

int solution(int n, vector<vector<int>> lighthouse) {
    int answer = 0;
    vector<vector<int>> lights(n + 1);
    for (vector<int> house : lighthouse) {
        lights[house[0]].push_back(house[1]);
        lights[house[1]].push_back(house[0]);
    }

    // DFS로 자신과 연결된 등대들의 상태를 보고 자신이 켤지 말지 결정한다.
    vector<bool> light_on(n + 1, false);
    vector<bool> visited(n + 1, false);
    dfs(1, lights, light_on, answer, visited);

    return answer;
}