[알고리즘/프로그래머스] 양과 늑대 (Lv.3)

 

[ 문제이해 ]

문제의 기본 유형은 이진 트리 모양의 초원에 각 노드마다 양 또는 늑대가 한마리씩 놓여있다.

이때, 루트 노드에서 출발하여 각 노드를 돌아다니면서 노드에 있는 동물을 데리고 다니는데 양의 수가 늑대의 수보다 항상 많아야 한다.

만약 늑대의 수가 더 많다면 양은 모두 잡아먹혀 양은 0마리가 된다.

또한, 한번 방문한 노드를 다시 방문할 수 있고, 중간에 양이 잡아 먹히지 않으면서 가장 많은 수의 양을 모으는 경우에서 양의 수를 결과값으로 내면 된다.

 

[ 문제풀이 ]

사실 문제 자체는 어렵지 않아 처음 문제를 접했을 때, 간단한 DFS문제로 해결하면 되는 줄 알았다.

하지만 보통의 DFS의 경우 한번 방문한 노드의 경우 다시 방문하지 않는다.

이 문제에서는 방문한 노드를 다시 방문해도 되지만 항상 양의 수가 많은 경우만을 생각해야 되서 조금 이해하기가 어려웠다.

 

또한 시간복잡도의 경우, info의 길이가 최대 17이기 때문에 모든 노드를 방문한다고 해도 시간적으로 문제가 되어 보이지는 않았다.

 

정리하고 보니 문제는 사실 DFS에서 조건을 잘 추가한다면 쉽게 해결될 수 있었던 문제였다.

먼저 기존의 DFS에서 방문처리를 해주는 visited 배열의 경우 이번 문제에서는 필요가 없다. 그래서 이 문제가 어려웠던 점은 기존의 DFS에서 사용하는 visited 배열을 사용하지 않고, 다음에 어떤 노드를 방문해야 하는지에 대한 정보를 알 수 없었기 때문이었다.

나는 이 문제를 아래의 몇가지 벡터를 활용하여 해결하였다.

1. 각 노드들이 연결되어 있는 상태를 저장한 map 벡터( 2차원 벡터로 연결하였다. )

2. 각 노드의 번호에 어떤 동물이 존재하는지 저장하는 animInfo 배열

3. 현재 노드와 연결되어 있고 이동할 수 있는 노드들의 정보를 저장한 nextNode 배열

 

그렇다면 위의 세가지를 어떤 방법으로 구성했는지 확인해보자.

#1. 각 노드들이 연결되어 있는 상태를 저장한 map 벡터

 

보통 DFS, BFS와 같은 그래프 문제를 풀 때 가장 먼저 해야하는 일이 문제에서 주어진 조건과 입력들을 내가 활용할 수 있는 형태로 저장하는 것이 제일 중요했다.

 

나의 경우에는 아래와 같이 배열을 정의하고 초기화 및 정보 저장을 진행하였다.

vector<vector<int>> map;

int solution(vector<int> info, vector<vector<int>> edges)
{
	map.resize(info.size());
    
    for(int i=0; i<edges.size(); i++)
    	map[edges[i][0]].push_back(edges[i][1]);
        
}

 

위의 코드에서 보면 map을 먼저 info.size()로 resize를 진행하였는데 이것은 map[i]라는 것은 i번째 노드와 연결되어 있는 노드들을 나타내기 위해서로, 전체 노드의 개수는 info의 개수와 같았기 때문이다.

그후, i와 j가 연결되어 있다는 것을 알기 위해, 반복문을 통해 map에 정보를 저장하였다.

 

#2. 각 노드의 번호에 어떤 동물이 존재하는지 저장하는 animInfo 배열

 

이 내용은 사실 어려운 내용이 아닌것이, info의 내용을 그대로 가져가면 되는 것이었다.(따로 초기화를 해줄 필요는 없었지만, 전역변수로 편하게 사용하기 위해서 한 행동인 것 같다.)

 

#3. 현재 노드와 연결되어 있고 이동할 수 있는 노드들의 정보를 저장한 nextNode 배열

 

이 부분이 가장 중요했는데 현재 노드와 연결되어 있는 모든 점들을 nextNode에 넣어주었다.(처음 시작할 때는 0번과 연결되어 있는 노드다.)

사실 본 함수에서는 중요하지 않는데 DFS를 진행하면서 왜 중요한 부분인지 알 수 있다.

 

#4. DFS 진행

 

DFS의 경우, 다른 문제와 다르게 현재 함수에서 재귀적으로 진행하면서 매개변수로 가져가야 할 것들이 꽤 있었다.

 

• 현재 노드의 정보
• 현재까지 노드를 건너며 모은 동물의 수(양, 늑대)
• 현재 노드에서 다음으로 이동할 수 있는 노드의 정보

이렇게 세가지를 매개변수로 전달하면서 아래의 순서대로 함수를 작성하였다.

1. 현재 방문한 노드에 존재하는 동물이 무엇인지 판단하고 각 동물의 마리 수를 늘려주었다.

2. 만약 현재 노드까지 방문하였을 때, 늑대가 많다면 더이상 함수를 진행시키지 않고 return해주었다.

3. return이 되지 않았을때(양의 수가 많을 때) 지금까지 모은 양의 최대값과 현재 모은 양의 최대값을 비교하여 answer을 업데이트 해주었다.

4. 현재 노드를 방문한 시점에서 다음으로 이동할 수 있는 노드의 정보를 저장한 벡터에 다음으로 이동할 노드를 벡터에서 지운 뒤, 다음으로 이동할 노드와 연결되어 있는 노드들을 벡터에 추가시켜주었다.

5. 그후, 다음 노드를 방문하면 된다.

 

DFS를 진행한 모든 코드는 아래와 같다.

void dfs(int curNode, int wolf, int sheep, vector<int> nextNode )
{
    int anim = animInfo[curNode];
    if(anim)
        wolf++;
    else
        sheep++;
    
    if(wolf >= sheep)
        return;
    
    answer = max(answer, sheep);
    
    for(int i=0; i<nextNode.size(); i++)
    {
        vector<int> next = nextNode;
        next.erase(next.begin() + i);
        int nxNode = nextNode[i];
        for(int j=0; j<map[nxNode].size(); j++)
        {
            next.push_back(map[nextNode[i]][j]);
        }
        dfs(nxNode, wolf, sheep, next);
    }
    
}

 

 

 

[ 전체 코드 ]

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

using namespace std;

int answer = 1;
vector<vector<int>> map;
vector<int> animInfo;
vector<int> nextNode;
queue<int> q;

void dfs(int curNode, int wolf, int sheep, vector<int> nextNode )
{
    int anim = animInfo[curNode];
    if(anim)
        wolf++;
    else
        sheep++;
    
    if(wolf >= sheep)
        return;
    
    answer = max(answer, sheep);
    
    for(int i=0; i<nextNode.size(); i++)
    {
        vector<int> next = nextNode;
        next.erase(next.begin() + i);
        int nxNode = nextNode[i];
        for(int j=0; j<map[nxNode].size(); j++)
        {
            next.push_back(map[nextNode[i]][j]);
        }
        dfs(nxNode, wolf, sheep, next);
    }
    
}
int solution(vector<int> info, vector<vector<int>> edges) {
    
    animInfo = info;
    
    map.resize(info.size());
    for(int i=0; i<edges.size(); i++)
        map[edges[i][0]].push_back(edges[i][1]);
    
    for(int i=0; i<map[0].size(); i++)
       nextNode.push_back(map[0][i]);
    
    dfs(0, 0, 0, nextNode);
    return answer;
}

 

 

---

이 문제는 사실 정리해보면 어렵지 않은 문제였지만, 다양한 조건들이 추가되어있어서 정리한것 처럼 글로 따로 정리해보기 전에는 매우 머리가 복잡했던 문제였다.