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

 

문제

문제 설명

 

풀이

 

[풀이]

 

처음에 모든 경우를 구하면 시간이 많이 오래 걸릴 것 같아서 어떻게 해야할까 생각했는데 제한사항에 info의 길이가 17밖에 되지 않는 것을 보고 충분히 완전탐색해도 되겠다는 생각이 들었다.

​

첫 노드부터 시작해 갈 수 있는 노드를 구해서 그 노드를 방문하도록 재귀적으로 코드를 짰다.

만약 특정 노드를 방문했는데, 양의 수와 늑대의 수가 같아지면 그 때는 더 이상 재귀를 하지 않도록 했다.

​

[아이디어 정리]

1. 방문할 수 있는 노드들을 vector로 정리해둔다.​ 
2. 새 노드를 방문 할 때마다 다음에 갈 수 있는 노드들을 새로 갱신한다.
3. 만약 새 노드를 방문했을 때, 늑대의 수가 양의 수와 같아지면 그 루트에서는 양이 잡아먹혔으므로 더 이상 탐색을 하지 않는다.
4. 이 잡아먹히지 않는 경우 중 가장 양의 수가 많았을 때를 return 한다

 

 

Code

 

 

#include <string>
#include <vector>
using namespace std;

// 길이가 짧으므로 완전 탐색해도 됨
vector<vector<int>> graph;
vector<int> realInfo;
vector<bool> canVisit;
int maxSheep=0;
void calc(int sheep, int wolf)
{
    if (maxSheep<sheep)
    {
        maxSheep=sheep;
    }
    if (sheep>wolf)
    {   
        for (int i=0; i<canVisit.size(); i++)
        {
            if (canVisit[i])
            {
                canVisit[i]=false; // 방문처리
                for (int j=0; j<graph[i].size(); j++)
                {
                    canVisit[graph[i][j]]=true; // 갈 수 있는 곳 표시
                }
                if (realInfo[i]==0) // 현재 방문한 곳이 양이면 양의 수 +1
                {
                    calc(sheep+1, wolf);
                }
                else // 방문한 곳이 늑대면 늑대의 수 +1
                {
                    calc(sheep, wolf+1); 
                }
                for (int j=0; j<graph[i].size(); j++)
                {
                    canVisit[graph[i][j]]=false;
                }
                canVisit[i]=true;
            }
        }
    }
}

int solution(vector<int> info, vector<vector<int>> edges) {
    int answer = 0;
    realInfo= info;
    graph = vector<vector<int>>(info.size());
    canVisit = vector<bool>(info.size(),false);
    for (int i=0; i<edges.size(); i++)
    {
        graph[edges[i][0]].push_back(edges[i][1]);
    }
    for (int i=0; i<graph[0].size(); i++)
    {
        canVisit[graph[0][i]]=true;
    }
    calc(1, 0);
    return maxSheep;
}

 

---

 

제한이 빡세지 않아 쉽게 풀 수 있는 문제였다.

 

프로그래머스