[ 프로그래머스 양과늑대 (Lv3) ] (C++)

프로그래머스의 양과 늑대(Lv3) 문제이다.

 

[ 문제풀이 ]

늑대에게 잡아먹히지 않으면서 양을 최대로 몇 마리까지 모아서 루트로 다시 돌아올 수 있는지 구해야 하는 문제이다.

문제에 접근하는 방법부터 정답을 도출하는 과정까지 순차적으로 진행해보자.

 

#1. 연결 관계

본인은 가장 먼저 노드들 간의 연결관계에 대해서 표시를 해 주었다.

vector 배열을 이용해서 노드들 간의 연결관계를 양방향으로 표시해 주었다.

양방향으로 표시를 했다는 것은, 예를 들어서 A번 노드와 B번 노드가 연결되어 있을 때, A번 노드와 연결되어 있는 노드에 B를 포함시켜주었고, 반대로 B번 노드와 연결되어 있는 노드에 A를 포함시켜 주었다는 것을 의미한다.

이렇게 양방향성으로 표시를 해준 이유는 "나에게 왔던 노드로 다시 돌아갈 수도 있기 때문"이다. 가장 쉽게, 루트노드에서 시작해서 루트노드의 자식노드로 이동했다고 가정해보자. 그 이후에 자식노드에서도 다시 루트노드로 갈 수 있고 가야만 하는 문제이기 때문에 이렇게 양방향성으로 구현해 주었다.

노드간의 연결관계를 나타내는 소스코드를 다음과 같이 구현하였다.

vector<int> node[20];

void makeConnection(vector<vector<int>> edges) {
	for (auto n : edges) {
		node[n[0]].push_back(n[1]);
		node[n[1]].push_back(n[0]);
	}
}

 

#2. 탐색 및 정답도출

본인은 이 과정을 완전탐색, 완전탐색 중에서도 깊이우선탐색(DepthFirstSearch : DFS)를 이용해서 접근해 보았다.

DFS 탐색에 사용되는 재귀함수에서는 3개의 매개변수를 사용해 주었다.

1. 현재 노드의 번호

2. 지금까지 따라온 양의 수

3. 지금까지 따라온 늑대의 수

위와 같이 3개의 매개변수를 사용해 주었다.

완전탐색을 진행할 때에는 중복된 탐색에 대한 체크가 중요하다. 이 문제에서도 마찬가지이다.

하지만, 단순히 해당 노드를 방문했는지 안했는지만으로는 중복체크를 할 수가 없다. 만약에, 해당 노드를 방문 했냐 안했냐로만 따진다면 이 문제의 정답을 구할 수가 없을 것이다. 왜냐하면, 우리는 Root노드를 계속해서 방문을 하면서 최대한 많은 수의 양을 구해야 하는데 Root노드를 처음에 한번 방문했다는 이유로 더 이상 방문하지 못하게 한다면 정답을 구할 수 없기 때문이다.

 

본인은 이를 위해서 boolean형 visit배열을 3차원으로 만들어주었다. 즉, 3차원 배열을 하나 만들어서 중복된 탐색에 대해서 체크를 해 주었다. 3차원 배열은 다음과 같은 의미를 가지게 된다.

visit[A][B][C] = true : A번 노드에 양을 B마리 늑대를 C마리를 데리고 방문한 적이 있습니다.

visit[A][B][C] = false : A번 노드에 양을 B마리 늑대를 C마리를 데리고 방문한 적이 없습니다.

이 배열을 가지고 DFS 탐색을 진행하게 될 것이다. 그리고, 위의 배열에 들어가는 'A','B','C'는 우리가 위에서 이야기한 DFS 함수의 매개변수에 들어있는 정보들이다.

 

그럼 본격적으로 탐색을 하는 과정을 진행해보자.

우리는 탐색을 할 때, 3가지 경우를 마주치게 될 것이다.

1. 양이 있는 노드로 움직이려는 경우

2. 늑대가 있는 노드로 움직이려는 경우

3. 아무것도 없는 노드로 움직이려는 경우

초기 상태에서는 3번에 해당하는 노드가 없지만, 노드를 방문할 때 마다 해당 노드에 있는 양과 늑대들이 따라오기 때문에 노드가 비어지는 경우가 발생하게 된다. 따라서 위와 같이 3가지 경우가 마주하게 될 것이다.

그렇다면, 이 3가지에 대해서 구체적으로 어떻게 탐색을 해야 할지 이야기를 해보자.

1. 양이 있는 노드로 움직이려는 경우

이 경우에는 단순히 중복체크만 해주면 된다. 못가는 경우가 없기 때문이다.

2. 늑대가 있는 노드로 움직이려는 경우

이 경우에는 늑대의 수와 양의 수를 비교해 주어야 한다. 왜냐하면, 해당 노드로 방문을 함으로써 늑대의 수가 양의 수보다 같거나 많아지게 된다면 지금까지 모은 양을 모두 잃어버리게 되기 때문이다. 그렇게 되면 당연히 모을 수 있는 양의 최댓값을 구하지 못하게 될 것이다. 따라서, 이 경우에는 "현재 가진 양의 수 > 늑대의 수 + 1" 이라는 조건이 성립할 때에만 탐색을 해주면 된다.

물론 ! 중복체크도 반드시 해 주어야 한다.

3. 아무것도 없는 노드로 움직이려는 경우

이 경우에도 단순히 중복체크만 해주면 된다. 못가는 경우가 없기 때문이다.

 

본인은 위와 같이 이 3가지 경우에 대해서 DFS탐색을 진행해 주었다. 진행하는 과정에서, "현재 노드의 번호가 '0'번이면, 즉, 현재 노드가 Root노드라면 기존에 모았던 양의 최대 수와 비교해서 갱신" 해 주었다.

 

[ 소스코드 ]

#include <string>
#include <vector>
#include <algorithm>
 
using namespace std;
 
vector<int> node[20];
vector<int> state;
int maxSheep;
bool visit[20][20][20];
 
void makeConnection(vector<vector<int>> edges) {
    for (auto n : edges) {
        node[n[0]].push_back(n[1]);
        node[n[1]].push_back(n[0]);
    }
}
 
void dfs(int cur, int sheep, int wolf) {
    if (cur == 0) {
        maxSheep = max(maxSheep, sheep);
    }
 
    for (auto next : node[cur]) {
        if (state[next] == 0) {
            if (visit[next][sheep + 1][wolf] == false) {
                visit[next][sheep + 1][wolf] = true;
                state[next] = -1;
                dfs(next, sheep + 1, wolf);
                state[next] = 0;
                visit[next][sheep + 1][wolf] = false;
            }
        } else if (state[next] == 1) {
            if (visit[next][sheep][wolf + 1] == false && sheep > wolf + 1) {
                visit[next][sheep][wolf + 1] = true;
                state[next] = -1;
                dfs(next, sheep, wolf + 1);
                state[next] = 1;
                visit[next][sheep][wolf + 1] = false;
            }
        } else {
            if (visit[next][sheep][wolf] == false) {
                visit[next][sheep][wolf] = true;
                dfs(next, sheep, wolf);
                visit[next][sheep][wolf] = false;
            }
        }
    }
 
 
}
 
int solution(vector<int> info, vector<vector<int>> edges) {
    makeConnection(edges);
    state = info;
    state[0] = -1;
    visit[0][1][0] = true;
    dfs(0, 1, 0);
    return maxSheep;
}