[프로그래머스] 등대

문제

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

 

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

 

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

---

입력

• 2 ≤ n ≤ 100,000
• lighthouse의 길이 = n – 1
  • lighthouse 배열의 각 행 [a, b]는 a번 등대와 b번 등대가 뱃길로 연결되어 있다는 의미입니다.
    • 1 ≤ a ≠ b ≤ n
    • 모든 등대는 서로 다른 등대로 이동할 수 있는 뱃길이 존재하도록 입력이 주어집니다.

---

마땅한 풀이 법이 떠오르지 않아 1개의 등대만 불을 킬 때 가능한 모든 경우, 2개의 등대만 불을 킬 때 가능한 모든 경우, ... 이렇게 불을 켤 등대의 개수를 늘려가며 모든 뱃길이 안전해 지는 경우를 찾고자 했다.

즉, n = 8일 경우

[등대 1개만 불을 키는 경우] 

1 2 3 4 5 6 7 8

1 2 3 4 5 6 7 8

...

1 2 3 4 5 6 7 8

[등대 2개만 불을 키는 경우]

1 2 3 4 5 6 7 8

1 2 3 4 5 6 7 8

...

1 2 3 4 5 6 7 8

 

이처럼 모든 경우를 탐색하며 모든 뱃길이 안전해 지는 상황을 찾으면 종료하도록 구현하였다.

불을 킬 등대의 개수에 맞게 어떤 등대들에 불을 켤 지 순열, 조합을 사용하여 모든 경우를 탐색하고자 했다.

 

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

int n, a, b;
vector<int> edge[100001];
vector<int> lightOn(100001, 0);

//모든 뱃길이 안전해 지는지 확인
bool all_ㅣight_on() {
	for (int i = 1; i <= n; i++) {
		if (lightOn[i]) continue; //자신이 On인 경우
		bool flag = 0;
		for (int j = 0; j < edge[i].size(); j++) { //On과 연결돼 있는지 확인
			int neighbor = edge[i][j];
			if (lightOn[neighbor]) { flag = 1; break; }
		}
		if (!flag) return false; //하나라도 안전하지 않은 뱃길이 발견되면 false 반환
	}
	return true; //모든 뱃길이 안전한 경우 true 반환
}

int solution(int _n, vector<vector<int>> lighthouse) {
    int cnt = 1; //몇개의 등대에 불을 킬 것인지에 대한 변수
    n = _n;
	for (int i = 0; i < n - 1; i++) {
		a = lighthouse[i][0], b = lighthouse[i][1];
		edge[a].push_back(b);
		edge[b].push_back(a);
	}
    //n = 100,000 인 경우 뱃길이 일자로 연결되어 있는 경우 worst case는 50,000개의 불을 키는 것.
	while (cnt < 50001) {
		vector<int> temp(n, 0);
		for (int i = 0; i < cnt; i++) temp[i] = 1;
		do { //cnt개의 등대에 불을 켤 모든 경우의 수를 구하는 순열, 조합
			for (int i = 1; i <= n; i++) lightOn[i] = 0;
			int pick = 0;
			for (int i = 0; i < n; i++) {
				if (pick == cnt) break; //불을 킬 cnt개의 등대 선택 완료
				if (temp[i]) { lightOn[i + 1] = 1; pick++; }
			}
			if (all_ㅣight_on()) { return cnt; } //해당 조합으로 모든 뱃길이 안전해 진 경우
		} while (prev_permutation(temp.begin(), temp.end()));
		cnt++;
	}
}

 

예제 2개의 case는 통과했지만 제출 시 역시나 시간 초과가 발생했다 ㅎㅎ;

 

꼬박 5시간을 매달린 끝에 실마리를 찾아 문제를 해결할 수 있었다.

내가 생각해낸 풀이 법은 leaf node들을 제거하고 각 leaf node의 상태(bright/dark)에 맞게 parent node에 불을 밝히는 것을 문제의 조건을 만족할 때까지 반복하는 것이었다.

 

이 문제에서 leaf 노드(=등대)를 연결된 뱃길이 하나 뿐인 노드, leaf 노드와 연결된 노드를 parent노드라 하자.

 

문제에서 한 뱃길의 양쪽 끝 등대 중 적어도 하나는 켜져있어야 한다고 했기 때문에 leaf 노드와 parent 노드 중 하나의 등대는 반드시 불을 켜야한다.

이 때, 최소한의 등대만으로 모든 뱃길을 안전하게 만들어야 하기 때문에 최대한 많은 뱃길을 밝힐 수 있는 즉, 많은 뱃길과 연결된 등대에 불을 키는 것이 최선의 선택이 될 수 있는 것이다.

따라서,  하나의 뱃길만 밝힐 수 있는 leaf 노드보다는 여러개의 뱃길을 밝힐 가능성이 있는 parent에 불을 키는 것이다.

 

예제를 통해, 자세히 살펴보자.

n = 10, lighthouse = [ [4,1], [5,1], [5,6], [7,6], [1,2], [1,3], [6,8], [2, 9], [9,10] ]

 

 1번 등대와 6번 등대를 살펴보면, 4, 3번 등대와 7, 8 등대에 불을 키는 것보다 1, 6번 등대에 불을 키는 것이 효율적이라는 것을 알 수 있다. 따라서, 각 leaf 노드를 제거하고 각 leaf노드는 현재 불이 꺼져있는 상태이므로 parent 노드의 불을 켜주면 된다. 

 

 

이 시점에서 모든 뱃길이 안전해지며, 모든 뱃길의 양쪽 끝 중 하나는 불이 켜져있으므로 조건을 만족하게 된다.

만약 위 상황에서 조건이 만족되지 못했다면 leaf노드인 6,9는 현재 불이 켜져있으므로 parent 노드의 불을 밝힐 필요 없이 바로 제거하면 된다.

반복하는 과정을 요약하면 아래와 같다.

 

1.leaf노드들 찾기

2.leaf노드 제거하기

3.leaf노드가 dark이면 parent노드의 불 켜기

->예시에서 3,4 leaf노드에 의해 parent노드 중복 불켜기를 방지하기 위한 조건문을 잊지말자

4.앞의 1,2,3 단계를 진행한 후 문제의 조건을 만족하는지 확인

 

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

int n, a, b, ans;
vector<int> edge[100001], lightOn(100001);

void remove_child(int parent, int child) {
    auto iter = find(edge[parent].begin(), edge[parent].end(), child);
    edge[parent].erase(iter);
}

void find_leaf() {
    int leaf, parent, child;
    for (int i = 1; i <= n; i++)
        if (edge[i].size() == 1) { //1.leaf노드 찾기
            leaf = i;
            parent = edge[leaf][0];

            //2.leaf노드 제거
            remove_child(parent, leaf);
            edge[leaf].clear();

            //3.leaf노드가 off이면 parent노드 불 켜기
            if (!lightOn[leaf]) {
                if (!lightOn[parent]) {
                    lightOn[parent] = 1;
                    ans++;
                }
            }
        }
}

//문제 조건을 만족하는지 확인
bool check() {
    //allSafe : 모든 뱃길이 안전한지
    //satisfy : 뱃길의 양쪽 등대 중 적어도 하나는 켜있는지
    int allSafe = 1, satisfy = 1;
    for (int i = 1; i <= n; i++) {
        if (edge[i].empty()) continue;
        if (lightOn[i]) continue; //자신이 bright하여 안전
        bool flag = 0;
        for (int j = 0; j < edge[i].size(); j++) {
            int neighbor = edge[i][j];
            if (lightOn[neighbor]) flag = 1; //자신은 dark지만 bright와 연결되어 안전
            else satisfy = 0; //뱃길의 양쪽 등대 모두 dark인 경우
        }
        if (!flag) { return false; } //안전하지 않은 뱃길 존재
    }
    return allSafe & satisfy;
}

int solution(int _n, vector<vector<int>> lighthouse) {
    n = _n;
    for (int i = 0; i < n - 1; i++) {
        a = lighthouse[i][0], b = lighthouse[i][1];
        edge[a].push_back(b);
        edge[b].push_back(a);
    }
    //조건을 만족할 때 까지
    while (!check()) find_leaf();
    return ans;
}