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

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

프로그래머스

풀이

간단한 듯 했지만 상당히 어려운 문제였다...

모든 뱃길에 대해 등대 하나는 무조건 켜져 있어야 하는데, 이 때 켜야하는 최소한의 등대 수를 구하는 문제이다.

아이디어는,

1. 먼저 그래프를 만들어서 말단 등대와 연결된 등대는 무조건 켠 후,

2. 켜진 등대와 연결된 뱃길은 모두 제거하고 다시 그래프를 만들어서

3. 등대를 키는 작업을 모든 뱃길이 제거 될 때 까지 반복하는 것이다.

예시로 아래 그림과 같이 연결된 뱃길이 있을 때, 1번을 통해 찾은 등대는 1, 6, 12 번 등대이고 해당 등대가 포함된 뱃길을 제거하면 [2, 9], [9, 10], [10, 11] 뱃길이 남는다. 이 과정을 모든 뱃길을 제거할 때 까지 반복하면 최소 등대 수를 찾을 수 있다.

1번 과정에서 연결 등대가 1개 있고, 현재 등대가 켜져 있지 않고 연결된 등대 또한 켜져있지 않다 라는 조건이 필요하다.

예시로, 하나의 뱃길 [1, 2]만 존재할 때 두 번째 조건이 없다면(현재 등대가 켜져 있는지 검사하지 않으면) 1, 2등대 모두 켜게 된다.

 

2번 과정에서 lighthouse를 바로 erase할 수 없어서 while문을 사용했더니 시간 초과가 난다. 켜진 등대가 포함된 뱃길을 찾는 즉시 erase하면 인덱스가 변경되기 때문에 올바르게 뱃길을 제거할 수 없다.

따라서, 제거된 뱃길을 표시하는 removedRoad 해시를 사용해서 제거된 뱃길이 아닐 때만 그래프에 추가하도록 하였다.

 

리뷰

처음엔 리프 등대를 모두 켠 후, BFS를 통해 완전 탐색하면서 연결 등대가 켜져 있지 않다면 켜는 알고리즘을 구현했다. 근데 반례를 못찾아서 방법을 바꿨다. erase 또한 시간이 굉장히 오래 걸리는 방법이어서 해시를 사용하는 방법으로 전환했다.

#include <string>
#include <vector>
#include <iostream>
#include <unordered_map>

using namespace std;

int solution(int n, vector<vector<int>> lighthouse) {
    int answer = 0;
    // 등대 체크 해쉬
    unordered_map<int, int> hash;
    // 제거된 뱃길 해쉬
    unordered_map<int, int> removedRoad;
    int num = lighthouse.size();
    while (true){
        // 모든 뱃길이 제거됐는지 확인
        int sum=0;
        for (auto i:removedRoad){
            sum+=i.second;
        }
        if (sum==num) break;
        // 그래프 만들기
        vector<vector<int>> graph(n+1);
        for (int i=0; i<num; i++){
            if (!removedRoad[i]){
                graph[lighthouse[i][0]].push_back(lighthouse[i][1]);
                graph[lighthouse[i][1]].push_back(lighthouse[i][0]);
            }
        }

        for (int i=1; i<=n; i++) {
            // 리프 등대면 연결 등대 on
            if (graph[i].size()==1 && !hash[graph[i][0]] && !hash[i]) {
                hash[graph[i][0]]=1;
                answer++;
            }
        }
        
        // 켜진 등대랑 연결된 뱃길 제거
        for (int i=0; i<lighthouse.size(); i++){
            if (hash[lighthouse[i][0]] || hash[lighthouse[i][1]]){
                removedRoad[i]=1;
            } 
        }
    }
   
    return answer;
}