[C++][프로그래머스] 양과 늑대 🔥

프로그래머스

 

📄 문제

2진 트리 모양 초원의 각 노드에 늑대와 양이 한 마리씩 놓여 있습니다. 이 초원의 루트 노드에서 출발하여 각 노드를 돌아다니며 양을 모으려 합니다. 각 노드를 방문할 때 마다 해당 노드에 있던 양과 늑대가 당신을 따라오게 됩니다. 이때, 늑대는 양을 잡아먹을 기회를 노리고 있으며, 당신이 모은 양의 수보다 늑대의 수가 같거나 더 많아지면 바로 모든 양을 잡아먹어 버립니다. 당신은 중간에 양이 늑대에게 잡아먹히지 않도록 하면서 최대한 많은 수의 양을 모아서 다시 루트 노드로 돌아오려 합니다.

예를 들어, 위 그림의 경우(루트 노드에는 항상 양이 있습니다) 0번 노드(루트 노드)에서 출발하면 양을 한마리 모을 수 있습니다. 다음으로 1번 노드로 이동하면 당신이 모은 양은 두 마리가 됩니다. 이때, 바로 4번 노드로 이동하면 늑대 한 마리가 당신을 따라오게 됩니다. 아직은 양 2마리, 늑대 1마리로 양이 잡아먹히지 않지만, 이후에 갈 수 있는 아직 방문하지 않은 모든 노드(2, 3, 6, 8번)에는 늑대가 있습니다. 이어서 늑대가 있는 노드로 이동한다면(예를 들어 바로 6번 노드로 이동한다면) 양 2마리, 늑대 2마리가 되어 양이 모두 잡아먹힙니다. 여기서는 0번, 1번 노드를 방문하여 양을 2마리 모은 후, 8번 노드로 이동한 후(양 2마리 늑대 1마리) 이어서 7번, 9번 노드를 방문하면 양 4마리 늑대 1마리가 됩니다. 이제 4번, 6번 노드로 이동하면 양 4마리, 늑대 3마리가 되며, 이제 5번 노드로 이동할 수 있게 됩니다. 따라서 양을 최대 5마리 모을 수 있습니다.

각 노드에 있는 양 또는 늑대에 대한 정보가 담긴 배열 info, 2진 트리의 각 노드들의 연결 관계를 담은 2차원 배열 edges가 매개변수로 주어질 때, 문제에 제시된 조건에 따라 각 노드를 방문하면서 모을 수 있는 양은 최대 몇 마리인지 return 하도록 solution 함수를 완성해주세요.

 

❗️ 제한사항

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

 

📝 풀이

• 스스로 해결하지 못해 아래의 글을 참고하여 문제를 이해하였습니다.

[C++] Programmers 양과 늑대 (2022 KAKAO Blind Recruitment)

· 틀린 코드 (72.2점)

• DFS를 이용하여 각 노드를 방문 시 연결된 모든 노드와, 방문했던 노드를 돌아가는 코드를 추가하여 모든 경우의 수를 검사하려했으나, 중복된 노드를 방문 시 wolf, sheep을 늘리는 문제와 복잡도가 증가하여 해결할 수 없었습니다.

#include <string>
#include <vector>
#include <climits>

using namespace std;

vector<bool> visit;
vector<bool> backed;
vector<vector<int>> graph;
vector<vector<int>> backing;
int answer = INT_MIN;

void dfs(int sheep, int wolf, int node, vector<int> info) {
    if(sheep == wolf)
    {
        printf("종료\n");
        return;
    }
        
    answer = max(answer, sheep);
    
    printf("[%d] %d, %d\n", node, sheep, wolf);
    
    if(node != 0)
    {
        printf("뒤로가기: [%d]->", node);
        backed[node] = true;
        dfs(sheep, wolf, backing[node][0], info);
        backed[node] = false;
    }
    
    for(int i = 0; i < graph[node].size(); ++i) {
        int next = graph[node][i];
        
        if(backed[next])
        {
            dfs(sheep, wolf + 1, next, info);
            continue;
        }
        
        if(visit[next] || next == node)
            continue;
        
        visit[next] = true;
        
        printf("[%d]->", node);
        
        if(info[next])
            dfs(sheep, wolf + 1, next, info);
        else
            dfs(sheep + 1, wolf, next, info);
        
        visit[next] = false;
    }
}

int solution(vector<int> info, vector<vector<int>> edges) {
    visit = vector<bool>(info.size(), false);
    backed = vector<bool>(info.size(), false);
    backing = vector<vector<int>>(edges.size() + 1, vector<int>());
    graph = vector<vector<int>>(edges.size() + 1, vector<int>());
    
    for(vector<int> edge : edges)
    {
        graph[edge[0]].push_back(edge[1]);
        graph[edge[1]].push_back(edge[0]);
    }
    
    for(vector<int> edge : edges)
        backing[edge[1]].push_back(edge[0]);
    
    visit[0] = true;
    dfs(1, 0, 0, info);
    
    return answer;
}

 

· 정답 코드

• DFS와 BFS를 결합하여 접근한 방식입니다.
• 큐를 활용하여 현재 노드에서 갈 수 있는 모든 노드를 삽입하여 이를 순서대로 방문합니다.
• 만약, wolf >= sheep인 경우, 더 나아갈 수 없기때문에 현재 위치를 큐에 삽입합니다.
  • ⭐ 현재 위치를 큐에 삽입하면, 다른 경로에서 sheep을 더 가져올 수 있습니다. 이를 통해 직전에 통과하지 못한 구간을 통과할 수 있게 됩니다.

// https://korini.tistory.com/40

#include <string>
#include <vector>
#include <algorithm>
#include <queue>

using namespace std;

vector<vector<int>> graph;
vector<int> _info;

int ans = 0;

void DFS(int cur, int sheep, int wolf, queue<int> q) 
{
    printf("%d\n", cur);
    
    // 현재 노드에 있는 양, 늑대를 계산
    if (_info[cur] == 0)
        sheep++;
    else
        wolf++;
    
    // 늑대가 더 많다면, 진행할 수 없음!
    if (wolf >= sheep)
        return;
    
    // 최대값 갱신
    ans = max(ans, sheep);
    
    // 현재 노드에서 갈 수 있는 모든 노드 삽입
    for (int i = 0; i < graph[cur].size(); i++) 
        q.push(graph[cur][i]);
    
    // 큐에 삽입된 순서대로 방문하기
    for (int i = 0; i < q.size(); i++) 
    {
        // 방문할 노드 가져오기
        int next = q.front();
        q.pop();
        
        // DFS 호출
        DFS(next, sheep, wolf, q);
        
        // DFS가 끝난 경우에 추후에 돌아오기 위해 대상 위치를 큐에 삽입
        // 삽입 전 queue의 다른 원소들을 방문하여 재시도 할 수 있음!
        q.push(next);
    }
}

int solution(vector<int> info, vector<vector<int>> edges) 
{
    // 단방향 그래프
    graph = vector<vector<int>>(info.size());
    
    // 전역 변수로 설정
    _info.assign(info.begin(), info.end());
    
    // 간선 정보 삽입
    for (int i = 0; i < info.size() - 1; i++)
        graph[edges[i][0]].push_back(edges[i][1]);
    
    queue<int> q;
    DFS(0, 0, 0, q);
    return ans;
}