[programmers] 양과 늑대

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

프로그래머스

---------------------------------------------------핵심 알고리즘--------------------------------------------

 

그래프 탐색, dfs

 

---------------------------------------------------풀이----------------------------------------------------

 

이 문제는 이진트리가 아니라 그래프를 탐색한다고 생각하고 풀면 쉽게 풀리는 문제이다.

기본 골자는 다음과 같다.

1. 현재 노드를 방문하였을 때, wolf와 sheep 수를 계산한다.

2. wolf >= sheep이면 양이 모두 잡아먹히므로 return 한다.

3. sheep > answer이면 answer를 갱신한다.

4. 현재 노드를 방문한 것으로 체크하고,(map 이용)

    방문한 모든 노드들에 대해서

    이웃한 노드들 중 방문하지 않은 노드들을 저장(child 노드들)

5. 저장한 노드들을 방문.

6. 노드를 방문하지 않은 것으로 변경.

#include <string>
#include <vector>
#include <map>
#include <iostream>

using namespace std;

vector<int> info;
int edges[18][2];
map<int, int> visited;
int answer = 0;

// 이진트리로 바꾸기.
void make_tree(vector<vector<int>> _edges){
    // 전체 초기화
    for(int i = 0; i < info.size(); i++){
        edges[i][0] = edges[i][1] = -1;
    }
    // 부모 노드에 child 노드 저장.
    for(int i = 0; i < _edges.size(); i++){
        if(edges[_edges[i][0]][0] == -1){
            edges[_edges[i][0]][0] = _edges[i][1];
        }
        else{
            edges[_edges[i][0]][1] = _edges[i][1];
        }
    }
}

// 최대 가능한 양 수 구하기
// 양의 수보다 늑대의 수가 같거나 더 많아지면 바로 잡아먹힘.
// 최대한 많은 수의 양을 모아서 루트로 돌아오려함.
// 현재 모은 최대의 양의 수를 리턴.
// 루트로 이동하더라도 다시 다른 노드로 이동 가능.
void find_max(int cur, int sheep, int wolf){
    // 현재 노드 방문
    if(info[cur]){
        wolf++;
    }
    else{
        sheep++;
    }
    // 종료되었는지 체크
    if(wolf >= sheep){
        return;
    }
    
    // 현재 양의 수가 큰 만큼 정답 갱신
    if(sheep > answer){
        answer = sheep;
    }
    
    visited[cur] = 1;
    
    // 트리가 아니라 그래프로 생각.
    // 방문한 노드들과 인접한, 방문하지 않은 노드를 전부 방문한다.
    vector<int> next_nodes;
    // 방문한 노드들에 대해
    for(auto it = visited.begin(); it != visited.end(); it++){
        // 인접한 노드 저장
        int n = it->first;
        for(int i = 0; i < 2; i++){
            // 없는 child나 이미 방문한 노드는 제외
            if(edges[n][i] < 0 || visited.find(edges[n][i]) != visited.end()) continue;
            next_nodes.push_back(edges[n][i]);
        }
    }
    // 저장한 노드 전부 순서대로 방문
    for(int i = 0; i < next_nodes.size(); i++){
        find_max(next_nodes[i], sheep, wolf);
    }
    
    auto it = visited.find(cur);
    visited.erase(it);
}

// 양 또는 늑대에 대한 정보 info, 각 노드들의 연결 관계 edges
int solution(vector<int> _info, vector<vector<int>> _edges) {
    info = _info;
    make_tree(_edges);
    
    find_max(0, 0, 0);
    return answer;
}

 

---------------------------------------------------후기----------------------------------------------------

 

이진트리를 어떻게 해야 효율적으로 탐색할 것인지를 고려하는 문제였다.

그러나, 여기서 함정에 빠지지 않아야 하는 점은, 이진트리라고 생각하면 안 된다는 것이다.

대놓고 함정을 파놓은 문제..가 아닐까....

여기서 이진트리로 생각하고 dfs를 돌리면서 생각하다 보면, 문제가 발생하는데,

바로 깊이만 들어가게 된다는 것이다. (그런 생각에 빠진다는거!ㅠㅠ)

이 문제는 친절한지 불친절한지 모르게,, 첫 예제부터 이렇게 풀면 안된다는 것을 명확히 보여준다.

0->1->4번을 탐색한 뒤, 4번이 아니라는 것을 깨닫고 8번을 탐색하러 가야하는데

이게 참 바보같은게 '그럼 어떻게 0번까지 돌아가서 다시 8번을 탐색하러 가지??'라는 생각을 하게 되면서

dfs...로 풀수 없는데 이걸 어떻게 풀지???라는 생각이 든다...(나만 그럴수도 있지만.......)

 

그래서 해결한 방식이

이진트리에서 벗어나는 것이다!

그저 그래프라고 생각하면, 이미 방문한 노드에 대해 인접한 노드들만 매번 탐색하고, 그걸 매번 다 탐색하더라도 최대 17개씩이었으니

무난하게 통과할 수 있다.

생각을 알고리즘에 갇히게 하지 말고,

문제 자체를 푼다고 생각하면서 알고리즘의 도움을 얻는게 핵심인 것 같다!!

퐈이팅..!