프로그래머스 문제 - 양과 늑대

프로그래머스 양과 늑대 문제 풀이를 진행하였습니다.

문제 해석

문제를 읽으면 아래와 같은 해석이 가능합니다.

2진 트리 모양 초원에 양과 늑대가 있는 노드들이 주어집니다.
각 노드에 들릴 때마다 그 노드에 있는 양과 늑대가 따라오게 됩니다.
양과 늑대의 수가 같거나 늑대가 더 많을 경우 양은 모두 죽게 됩니다.
주어진 트리 모양에서 얼마나 최대로 양을 데려올 수 있는지 출력해야 합니다.

문제 풀이

DFS를 사용하여 문제를 해결하였습니다.

일단 계산을 위하여 2진 트리를 배열에 넣어서 정리를 해줍니다.
무조건 시작 지점은 0번째이고 양이 존재하기 때문에 원활한 재귀를 위하여 처음만 계산해줍니다.

//그래프 입력
for(vector<int> v : edges)
{
    land[v[0]].push_back(v[1]);
}
    
//0번째가 시작지점이고 무조건 양이 있으므로 처음만 미리 계산
queue<int> q;
for(int t : land[0])
{
    q.push(t);
}

문제를 풀며 조심해야 할 점은 DFS를 통하여 답을 해결할 시 한번 검색했던 노드였어도 나중에 여러 번 검색하는 경우가 존재하는 점이였습니다.
이 부분은 queue배열을 사용하여 해결하였습니다.

일단 현재 자신의 노드를 cur변수에 저장한 후 제거해줍니다.
그리고 temp라는 새로운 배열 안에 cur을 제거한 배열의 변수들과 cur변수의 자식 노드들을 넣어준 후 바뀐 값으로 함수를 실행합니다.
그 후 기존 배열에 cur변수를 넣어줌으로서 이후 계산을 문제없이 해결할 수 있습니다.

q.pop();
//양의 다음 노드들의 정보를 저장 후 재귀로 검색
queue<int> temp = q;
for(int num : land[cur])
{
    temp.push(num);
}    
solve(sheep+1, wolf, temp);
//다음 계산을 위해 다시 넣어줌
q.push(cur);

전체 코드

이번 문제는 DFS를 사용하여 문제를 해결할 수 있었습니다.

#include <bits/stdc++.h>
#include <string>
#include <vector>

using namespace std;

vector<int> land[20];
vector<int> animalInfo;
int maxSheep = 0;

void solve(int sheep, int wolf, queue<int> q)
{
    //양의 최대값을 넣어줌
    if(maxSheep < sheep)
    {
        maxSheep = sheep;
    }
    
    int size = q.size();
    for(int i = 0; i < size; i++)
    {
        int cur = q.front();
        //양이 있을 경우
        if(animalInfo[cur] == 0)
        {
            q.pop();
            //양의 다음 노드들의 정보를 저장 후 재귀로 검색
            queue<int> temp = q;
            for(int num : land[cur])
            {
                temp.push(num);
            }    
            solve(sheep+1, wolf, temp);
            //다음 계산을 위해 다시 넣어줌
            q.push(cur);
        }
        else
        {
            //늑대가 양보다 같거나 많을 경우 계산 무시
            if(sheep <= wolf+1)
            {
                q.push(cur);
                q.pop();
            }
            else
            {
                q.pop();
                queue<int> temp = q;
                //늑대의 다음 노드들의 정보를 저장 후 재귀로 검색
                for(int num : land[cur])
                {
                    temp.push(num);
                }
                solve(sheep, wolf+1, temp);
                //다음 계산을 위해 다시 넣어줌
                q.push(cur);
            }
        }
    }
}

int solution(vector<int> info, vector<vector<int>> edges) {
    int answer = 0;
    animalInfo = info;

    //그래프 입력
    for(vector<int> v : edges)
    {
        land[v[0]].push_back(v[1]);
    }
    
    //0번째가 시작지점이고 무조건 양이 있으므로 처음만 미리 계산
    queue<int> q;
    for(int t : land[0])
    {
        q.push(t);
    }
    solve(1, 0, q);
    answer = maxSheep;
    
    return answer;
}

출저

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