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

해설

DFS문제이다. 먼저 연결되어 있는 노드를 정리해주고 1부터 노드를 탐색한다.

나와 연결되어있는 노드가 둘 다 켜지지 않았다면 우선적으로 나의 불을 켜주는 식으로 진행한다. 

DFS문제를 많이 풀어봤다면 어렵지 않은 문제인것 같다.

---

문제 설명

인천 앞바다에는 1부터 n까지 서로 다른 번호가 매겨진 등대 n개가 존재합니다. 등대와 등대 사이를 오가는 뱃길이 n-1개 존재하여, 어느 등대에서 출발해도 다른 모든 등대까지 이동할 수 있습니다. 등대 관리자 윤성이는 전력을 아끼기 위하여, 이 중 몇 개의 등대만 켜 두려고 합니다. 하지만 등대를 아무렇게나 꺼버리면, 뱃길을 오가는 배들이 위험할 수 있습니다. 한 뱃길의 양쪽 끝 등대 중 적어도 하나는 켜져 있도록 등대를 켜 두어야 합니다.

예를 들어, 아래 그림과 같이 등대 8개와 7개의 뱃길들이 있다고 합시다. 이 경우 1번 등대와 5번 등대 두 개만 켜 두어도 모든 뱃길은 양쪽 끝 등대 중 하나가 켜져 있으므로, 배들은 안전하게 운항할 수 있습니다.

등대의 개수 n과 각 뱃길이 연결된 등대의 번호를 담은 이차원 배열 lighthouse가 매개변수로 주어집니다. 윤성이가 켜 두어야 하는 등대 개수의 최솟값을 return 하도록 solution 함수를 작성해주세요.

---

코드

#include <string>
#include <vector>

using namespace std;

int answer = 0;
bool LighthouseOn[100001];

void DFS(int CurNode, int ConnectedNode, const vector<vector<int>>& way)
{
    for(int i=0; i< way[CurNode].size(); i++)
    {
        if(way[CurNode][i] != ConnectedNode)
        {
            DFS(way[CurNode][i], CurNode, way);
            
            if(!LighthouseOn[way[CurNode][i]] && !LighthouseOn[CurNode])
            {
                answer++;
                LighthouseOn[CurNode] = true;
            }
        }
    }
}

int solution(int n, vector<vector<int>> lighthouse) {    
    vector<vector<int>> Way(n+1);
    
    for(int i=0; i<lighthouse.size(); i++)
    {
        Way[lighthouse[i][0]].push_back(lighthouse[i][1]);
        Way[lighthouse[i][1]].push_back(lighthouse[i][0]);
    }
    
    DFS(1,1,Way);
    
    return answer;
}