프로그래머스: 양과 늑대⭐⭐⭐

난이도 ⭐⭐⭐
유형 : 탐색, 자료구조

🧐 문제

문제 설명

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번 노드는 항상 루트 노드입니다.

---

입출력 예

info	edges	result
[0,0,1,1,1,0,1,0,1,0,1,1]	[[0,1],[1,2],[1,4],[0,8],[8,7],[9,10],[9,11],[4,3],[6,5],[4,6],[8,9]]	5
[0,1,0,1,1,0,1,0,0,1,0]	[[0,1],[0,2],[1,3],[1,4],[2,5],[2,6],[3,7],[4,8],[6,9],[9,10]]	5

---

입출력 예 설명

접기/펼치기

입출력 예 설명

입출력 예 #1

문제의 예시와 같습니다.

입출력 예 #2

주어진 입력은 다음 그림과 같습니다.

0번 - 2번 - 5번 - 1번 - 4번 - 8번 - 3번 - 7번 노드 순으로 이동하면 양 5마리 늑대 3마리가 됩니다. 여기서 6번, 9번 노드로 이동하면 양 5마리, 늑대 5마리가 되어 양이 모두 잡아먹히게 됩니다. 따라서 늑대에게 잡아먹히지 않도록 하면서 최대로 모을 수 있는 양은 5마리입니다.

---

🔍 힌트

0번 노드에서 내려올때, 갈 수 있는 모든 노드들을 저장해둔다. 그런 후, 재귀적으로 모든 노드들에 방문하여야 한다.

종료 시점은 늑대와 양의 수가 같아졌을 때로 두면 된다.

---

✏️ 나의 풀이

#include <bits/stdc++.h>

#include <bits/stdc++.h>

using namespace std;

vector<pair<int,int>> edges[17];
int result = INT_MIN;

// input으로 들어왔던 edges 변형시키기
// edge 내에 양인지 늑대인지에 대한 정보도 함께 넣는다.
void set_edges(vector<int> input_info, vector<vector<int>>& input_edges) {
    for(vector<int> input_edge : input_edges) {

        int sheep = input_info[input_edge[1]] == 0 ? 1 : -1;

        edges[input_edge[0]].push_back(
            make_pair(input_edge[1], sheep)
        );
    }
}

// next: 간적 없는 간선 벡터
// sheeps: 현재까지의 양의 수
// cnt: 양과 늑대의 수를 체크하기 위한 변수
void bfs(vector<pair<int,int>> next, int sheeps, int cnt) {

    // 양과 늑대의 수가 같아지면 return
    if(cnt < 1) return;

    // 갈 노드를 하나 선택 -> 해당 노드에서 갈 수 있는 노드를 next에 추가
    for(int i=0; i<next.size(); i++) {
        // 다음 노드 선정
        pair<int, int> next_node = next[i];
        
        // next 벡터를 복사한 뒤, 현재 노드는 삭제
        vector<pair<int,int>> next_copy = next;
        next_copy.erase(next_copy.begin() + i);
        
        // 다음 노드와 연결된 노드 추가
        next_copy.insert(next_copy.end(), edges[next_node.first].begin(), edges[next_node.first].end());

        // 양의 수를 조정하고 다음 노드로
        int next_sheeps = next_node.second == 1 ? sheeps + 1 : sheeps;
        bfs(next_copy, next_sheeps, cnt + next_node.second);
    }

    result = max(result, sheeps);
}

int solution(vector<int> input_info, vector<vector<int>> input_edges) {
    set_edges(input_info, input_edges);

    bfs(edges[0], 1, 1);

    return result;
}

✔️ 다른 사람의 풀이

def solution(info, edges):
    visited = [0] * len(info)
    answer = []
    
    def dfs(sheep, wolf):
        # 양의 수가 많을 때마다 따로 저장해두고 있다.
        # max 함수를 쓰면, 최적화에 더 좋지 않을까?
        if sheep > wolf:
            answer.append(sheep)
        else:
            return 
        
        # 입력으로 제공된 edges를 매번 순회하고 있다.
        # p: 부모, c: 자식
        for p, c in edges:
            # 제공된 edges를 그대로 순회하기에 부모 노드의 방문 여부를 조사하고 있다.
            # 자식 노드를 방문한 적이 없을때
            if visited[p] and not visited[c]:
                # visited[c]를 1로 바꿨다 0으로 바꿨다하는 것은,
                # 백트래킹의 특징이다.
                visited[c] = 1
                if info[c] == 0:
                    dfs(sheep+1, wolf) # 양일때
                else:
                    dfs(sheep, wolf+1) # 늑대일때
                visited[c] = 0

	# 루트 노드부터 시작
	visited[0] = 1
    dfs(1, 0)

    return max(answer)

🧐 분석

1. 양의 수가 많을때마다 answer 배열에 추가해주고 있다.
2. 입력으로 제공된 edges를 매번 순회하고 있다. 그로 인해 부모의 방문 여부를 조사하고 있다.
3. 백트래킹을 사용하고 있다.

📜 재구현

#include <bits/stdc++.h>
#define fastio cin.tie(0)->sync_with_stdio(0)

using namespace std;

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

    vector<bool> visited(info.size());
    auto dfs = [&](int sheep, int wolf, auto&& dfs) -> void {

        if(sheep > wolf) answer = max(answer, sheep);
        else return;

        for(vector<int> edge : edges) {
            int p = edge[0];
            int c = edge[1];

            if(visited[p] && !visited[c]) {
                visited[c] = true;

                if(info[c] == 0) dfs(sheep+1, wolf, dfs);
                else dfs(sheep, wolf+1, dfs);

                visited[c] = false;
            }
        }

    };
    visited[0] = 1;
    dfs(1, 0, dfs);

    return answer;
}

python을 c++로 그대로 옮겨봤다.
백트래킹으로 구현해보는건 생각못했는데, 덕분에 좋은 아이디어를 얻었다.

Programmers 카테고리 내 다른 글 보러가기