[프로그래머스/Level 3/C++/2022 카카오 블라인드 채용] 양과 늑대

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

- 출처 : 프로그래머스 코딩 테스트 연습

프로그래머스

 

[문제 요약]

- 2진 트리 모양 초원의 각 노드에 늑대와 양이 한 마리씩 놓여 있습니다. 이 초원의 루트 노드에서 출발하여 각 노드를 돌아다니며 양을 모으려 합니다. 각 노드를 방문할 때 마다 해당 노드에 있던 양과 늑대가 당신을 따라오게 됩니다.

- 이때, 늑대는 양을 잡아먹을 기회를 노리고 있으며, 당신이 모은 양의 수보다 늑대의 수가 같거나 더 많아지면 바로 모든 양을 잡아먹어 버립니다.

- 당신은 중간에 양이 늑대에게 잡아먹히지 않도록 하면서 최대한 많은 수의 양을 모아서 다시 루트 노드로 돌아오려 합니다.

[문제 조건]

• 2 ≤ info의 길이 ≤ 17
  • info의 원소는 0 또는 1 입니다.
  • info[i]는 i번 노드에 있는 양 또는 늑대를 나타냅니다.
  • 0은 양, 1은 늑대를 의미합니다.
  • info[0]의 값은 항상 0입니다. 즉, 0번 노드(루트 노드)에는 항상 양이 있습니다.
• edges의 세로(행) 길이 = info의 길이 - 1
  • edges의 가로(열) 길이 = 2
  • edges의 각 행은 [부모 노드 번호, 자식 노드 번호] 형태로, 서로 연결된 두 노드를 나타냅니다.
  • 동일한 간선에 대한 정보가 중복해서 주어지지 않습니다.
  • 항상 하나의 이진 트리 형태로 입력이 주어지며, 잘못된 데이터가 주어지는 경우는 없습니다.
  • 0번 노드는 항상 루트 노드입니다.

 

 

[문제 풀이]

문제를 읽어보면 알겠지만 단순한 탐색 방법이 적용될지 안될지 그런 생각이 드는 문제다. 

 

왜냐하면 아주 단순하게 왼쪽으로 탐색하다가 다시 돌아와서 오른쪽으로 탐색하고 하는 방식, 경로를 이용해 문제를 접근하면 느낌상 시간초과가 날 것 같은 문제다.

 

그래서 필자는 현재 상태에서 방문 할 수 있는 노드들의 집합을 가지고 탐색하면서 가질 수 있는 양의 최대값을 갱신하면서 답을 구하였다.

 

그림으로 한번 나타내보면

 

현재 처음 위치인 0에서 갈 수 있는 곳은 하나, 2번으로 갈 수 밖에 없다. 왜냐하면 1번으로 가게 되면 양과 늑대의 수가 같아져 먹혀버리기 때문이다.

 

여기서 중요한 점은 지금 상태에서 1번으로 갈 수 없다는거지 어딘가를 탐색하다가 양의 수가 늘어나면 1번을 탐색할 수 있게 될지도 모른다. 따라서 탐색을 할때 방문가능한 노드들에 대한 정보는 계속 들고다녀야 한다.

 

이 다음 2를 방문한 상태에서 갈 수 있는 노드는 {1, 5, 6} 노드가 있다. 

전에 0번 노드에 있을 때는 1번노드를 탐색할 수 없었지만 2번 노드를 탐색한 후에는 양이 늘었기 때문에 탐색할 수 있게 되었다.

 

위와 같은 방식으로 탐색을 진행하면서 양의 수를 계속해서 최대로 갱신시켜주고 탐색이 종료된 뒤에 이 값이 정답이 되게 된다.

 

[소스 코드]

#include <string>
#include <queue>
#include <vector>
#include <list>
#include <iostream>

using namespace std;

vector<int> info2;
int answer = 0;

void dfs(int cur, int cur_sheep, int cur_wolf, vector<int> can_visit, vector<vector<int>> &graph)
{
    answer = max(answer, cur_sheep);
    for(int i=0; i<can_visit.size(); i++)
    {
        vector<int> tmp = can_visit;
        tmp.erase(tmp.begin() + i);
        for(int j=0; j<graph[can_visit[i]].size(); j++)
            tmp.push_back(graph[can_visit[i]][j]);
        
        if(info2[can_visit[i]] == 0)
            dfs(can_visit[i], cur_sheep+1, cur_wolf, tmp, graph);
        else
        {
            if(cur_sheep <= cur_wolf + 1) continue;
            else
                dfs(can_visit[i], cur_sheep, cur_wolf+1, tmp, graph);
        }
    }
}

int solution(vector<int> info, vector<vector<int>> edges) {
    vector<vector<int>> graph;
    info2 = info;
    graph.resize(info.size());
    
    for(int i=0; i<edges.size(); i++)
        graph[edges[i][0]].push_back(edges[i][1]);
    
    vector<int> tmp;
    for(int i=0; i<graph[0].size(); i++) tmp.push_back(graph[0][i]);
   
    dfs(0,1,0,tmp,graph);
    
    return answer;
}

이 문제에서 핵심은 시간초과 나지 않게 다음으로 방문 가능한 노드들을 들고 탐색을 진행하는 것이 핵심인 문제인거 같다. 

굳