코딩테스트 -- 등대 - (프로그래머스 / C++)

 

프로그래머스

 

문제요약!

---

 여러개의 지점들이 있고 각 지점들이 서로 연결되어있는 뱃길이 있다고 하였을때

두 지점중 한 지점에는 등대가 무조건 켜져 있어야 할때 

 

최소로 켜질 등대의 수를 구하는 문제!

 

이것 외에는 신경쓸 부분은 없어 보였습니다. 

---

 

문제를 보고 가장 먼저 생각난 경우는

1. 가장 많이 연결된 지점부터 키면서 탐색한다

2. 가장 끝부분 단말노드로 부터 탐색을 진행하며 등대를 켜준다

 

이렇게 두가지의 방법을 생각 할 수 있었습니다.

 

1번의 경우는 약간의 예외가 발생할 수 도 있을거라 생각하여

 

 

 

저는 2번의 방법으로 진행하기로 하였습니다. 

 

 

그럼 코드!

---

 

단말노드부터 탐색을 진행하기위해서

단말노드를 찾아 연결된 노드에 등대를 켜주고 다시 단말노드를 찾고를 반복해주려다

 

DFS를 통한 탐색으로 해결할 수 있을거라고 생각하여 코드를 작성해 주었습니다. 

 

 

가장 먼저 탐색을 위한 노드맵을 만들어주고 기준점인 1번등대부터 탐색을 시작해주었습니다. (시작위치는 어디든 상관 x)

int solution(int n, vector<vector<int>> lighthouse) {
    vector<vector<int>> lighthouse_Node(n + 1);

    for (int i = 0; i < lighthouse.size(); i++) { // 등대 양쪽 연결정보 저장!
        lighthouse_Node[lighthouse[i][0]].push_back(lighthouse[i][1]);
        lighthouse_Node[lighthouse[i][1]].push_back(lighthouse[i][0]);
    }


    dfs(1, 1, lighthouse_Node); // 1번등대부터 탐색

    return answer;
}

 

 

이제 여기부터는 깊이 탐색 시작!

 

코드상으로는 아래처럼 구성됩니다. 

bool Light_on[100001] = { 0 }; // 불이 켜진 등대인지 체크

void dfs(int child, int parent, vector<vector<int>>& lighthouse_Node) { 
// 끝에서부터 부모의 불을 켜주면? >> 단말노드부터 불을 켜주면서 설정

    for (int i = 0; i < lighthouse_Node[child].size(); i++) {

        if (lighthouse_Node[child][i] != parent) {// 연결되어있는지 확인

            // 연결되어있다면 자식의 자식의 자식으로 탐색 시작!
            dfs(lighthouse_Node[child][i], child, lighthouse_Node); 

            // 자식과 부모 등대 모두 불이 꺼져 있다면 부모 등대 불 켜주기
            if (!Light_on[lighthouse_Node[child][i]] && !Light_on[child]) {
                Light_on[child] = true;
                answer++;
            }
        }
    }
}

 

 

그림으로 확인해보면 가장 우측의 1번노드부터 탐색을 시작한다고 했을때

깊이 탐색을 이용하면 

 

 

순서대로 2 > 4 > 5 > 10 > 11 > .... 순서대로 탐색을 시작하게 됩니다.

(순서는 바뀔수 있지만 깊은부분부터 탐색을 한다는 것!)

 

 

 

 

그렇기에  탐색함수의 가장 하단부의 if부분은 각 단말노드인 4,6,10,11 부분부터 실행되게 됩니다. 

 // 자식과 부모 등대 모두 불이 꺼져 있다면 부모 등대 불 켜주기
            if (!Light_on[lighthouse_Node[child][i]] && !Light_on[child]) {
                Light_on[child] = true;
                answer++;
            }

 

 

그림으로 보면 아래처럼 4,6의 부모등대를 켜주고

10,11의 부모등대를 켜주는 순서로 실행됩니다!

 

 

 

이상으로 

 

단말노드부터 부모노드를 켜주면서 탐색을 진행하는 방법이였습니다!

 

 

 

 

틀린점이 있다면 댓 달아주세요!