개발기록장

양과 늑대

15 min read

문제 링크
난이도 : Lv. 3

문제 내용

문제 설명
문제 설명

2진 트리 모양 초원의 각 노드에 늑대와 양이 한 마리씩 놓여 있습니다. 이 초원의 루트 노드에서 출발하여 각 노드를 돌아다니며 양을 모으려 합니다. 각 노드를 방문할 때 마다 해당 노드에 있던 양과 늑대가 당신을 따라오게 됩니다. 이때, 늑대는 양을 잡아먹을 기회를 노리고 있으며, 당신이 모은 양의 수보다 늑대의 수가 같거나 더 많아지면 바로 모든 양을 잡아먹어 버립니다. 당신은 중간에 양이 늑대에게 잡아먹히지 않도록 하면서 최대한 많은 수의 양을 모아서 다시 루트 노드로 돌아오려 합니다.

03_2022_공채문제_양과늑대_01.png

예를 들어, 위 그림의 경우(루트 노드에는 항상 양이 있습니다) 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번 노드는 항상 루트 노드입니다.
입출력 예
infoedgesresult
[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

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

03_2022_공채문제_양과늑대_02.png

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

문제 분석

BFS처럼 하면 되지 않을까…?

작성한 코드

#include <string>
#include <vector>
#include <unordered_map>
#include <stack>
#include <iostream>
 
using namespace std;
 
int solution(vector<int> info, vector<vector<int>> edges) {
    // 여기서는 연결 리스트로 만들어 볼 것
    unordered_map<int, vector<int>> connectList;
    for(int i = 0; i < info.size(); i++)
    {
        connectList[i] = {};
    }
    for(int i = 0; i < edges.size(); i++)
    {
        connectList[edges[i][0]].push_back(edges[i][1]);
    }
    
    vector<int> checked(info.size(), 0);
    
    // 연결 리스트 완성
    
    // 스택 만들어서 다음에 갈 곳 관리
    stack<int> nextPosition;
    
    int sheeps = 0; 
    int wolves = 0; 
    
    int checkIndex = 0;
    
    do{
        cout << "Check Index : " << checkIndex;
        cout << "  Next Position Size : "<< nextPosition.size();
        cout << "  Sheeps : " << sheeps;
        cout << "  Wolves : " << wolves << endl;
        
        if(checked[checkIndex] == 1)
        {
            // 여기 왔던곳이면 뒤로감
            checkIndex = nextPosition.top();
            nextPosition.pop();
        }
        else 
        {
            checked[checkIndex] = 1;
            // 현위치 체크
            if(info[checkIndex] == 0)
                sheeps++;
            else
                wolves++;
 
            bool findSheep = false;
            // 다음에 어디로 갈지 체크
            for(int i = 0; i < connectList[checkIndex].size(); i++)
            {
                if(!findSheep)
                {
                    // 이번에 체크한 노드가 양이면 거기로 가기
                    if(info[connectList[checkIndex][i]] == 0)
                    {
                        checkIndex = connectList[checkIndex][i];
                    }
                    findSheep = true;
                }
                
                else
                // 이번에 체크한 노드가 양이 아니거나 이미 양이 있는 노드를 찾았으면 스택에 넣어둠
                {
                    if(i == connectList[checkIndex].size() - 1 && sheeps > wolves + 1)
                    {
                        checkIndex = connectList[checkIndex][i];
                    }
                    else 
                    {    
                        nextPosition.push(connectList[checkIndex][i]);
                    }
                    
                }
            }
        }
        
    }while(nextPosition.size() != 0);
    
    
    return sheeps;
}
  • 못맞췄음
  • 이유 : 그냥 DFS로 하면 안됐음…

챗지피티의 도움

❌ 왜 네 코드가 틀리는지 — 핵심 3가지 이유

1) 트리 경로를 한 방향으로만 탐색해서 틀림

너의 코드는

  • “현재 노드의 양이면 가고”

  • “아니면 스택에 넣고”

  • “양이 충분하면 마지막 노드로 이동”

이런 식으로 일종의 ‘탐색 우선순위’를 만들어서 하나의 경로로만 탐색 중임.

하지만 이 문제는 “특정 경로”로 가는 게 목적이 아님.

✔ 이 문제는 현재까지 방문 가능한 모든 노드를 후보로 두고, 그 중 하나를 선택해 계속 진행하는 방식으로 풀어야 함.
즉, 경로가 아니라 ‘상태 공간’을 탐색하는 문제임.

2) 노드를 ‘왔다갔다 할 수 있음’을 고려하지 않음

문제 조건:

  • 만약 현재까지 양 > 늑대,
    그 순간부터는 이미 방문했던 노드든 아니든, 그 노드의 자식은 언제든 다시 방문 가능임.

즉,
트리 구조라고 해서 “부모→자식” 순서로 고정적으로 움직이는 게 아님.

방문 가능한 모든 노드를 항상 후보로 다시 고려해야 함.

너의 방식은
“한 방향으로 내려갔다가 막히면 스택에서 돌아간다”
이런 단순 DFS라서 문제의 본질을 반영하지 못함.

3) 이 문제는 반드시 ‘현재 방문한 노드 집합’을 상태로 가지는 DFS가 필요함

문제의 정답률이 낮은 이유도 이것 때문.

상태는 다음처럼 표현해야 함:

(현재 노드, 현재까지 얻은 양, 현재까지 만난 늑대, 현재 방문 가능한 노드 목록)

즉, 단순 stack<int> 으로는 절대 해결 불가.
방문 가능 노드 세트가 필요함.

📌 예시로 설명 (문제의 대표 반례)

info = [0,0,1,1,1,0,1,0,1,0,1,1] edges = ...

이 경우 정답은 5인데,
단순 DFS로 가면 보통 3~4밖에 못 모음.

왜냐하면 양을 더 많이 얻기 위해서 잠시 늑대 쪽으로 갔다가 다시 돌아오는 선택이 필요함.

너의 코드는 이런 경우를 절대 처리 못 함.

✔️ 정답 풀이 구조는 이렇게 되어야 함

1. 현재 상태를 포함한 DFS:

void dfs(int node, int sheep, int wolf, vector<int> canVisit)

  • 현재 node

  • 현재까지 sheep/wolf 개수

  • 현재 방문 가능한 노드 리스트(canVisit)

2. canVisit에서 다음 방문 노드를 하나씩 선택해서 DFS 확장

3. 방문할 때마다 그 노드의 자식들을 canVisit에 추가함

이 구조가 정석임.

⭐ 검증된 정답 코드 (가장 대표적인 풀이)

#include <vector>
#include <algorithm>
 
using namespace std;
 
vector<vector<int>> graph;
int answer = 0;
 
void dfs(int node, int sheep, int wolf, vector<int> canVisit, vector<int>& info)
{
    if (info[node] == 0) sheep++;
    else wolf++;
 
    if (wolf >= sheep) return;
 
    answer = max(answer, sheep);
 
    // 현재 노드 방문했으니 제거
    canVisit.erase(find(canVisit.begin(), canVisit.end(), node));
 
    // 자식 노드를 canVisit에 추가
    for (int next : graph[node]) {
        canVisit.push_back(next);
    }
 
    // 방문 가능한 모든 노드에 대해 DFS 시도
    for (int next : canVisit) {
        dfs(next, sheep, wolf, canVisit, info);
    }
}
 
int solution(vector<int> info, vector<vector<int>> edges) {
    int n = info.size();
    graph.assign(n, {});
 
    for (auto& e : edges) {
        graph[e[0]].push_back(e[1]);
    }
 
    vector<int> canVisit = {0};
    dfs(0, 0, 0, canVisit, info);
 
    return answer;
}

📌 정리

네 코드가 틀리는 이유:

  1. 문제는 “트리를 한 방향으로 탐색”하는 문제가 아니라
    현재 방문 가능한 모든 노드를 선택지로 하는 상태 탐색(백트래킹) 문제임.

  2. 너의 방식은 “경로”만 탐색함 → 반드시 틀림.

  3. 이 문제는 canVisit 리스트가 핵심이며,
    단순 DFS + stack으로 절대 풀 수 없음.

그래서 뭐라고요?

  • 정답 알고리즘 요약
dfs(현재 노드, 양 개수, 늑대 개수, 방문 가능한 노드 리스트)
{
    1. 현재 노드의 동물 기록 (양/늑대++)
    2. 늑대 >= 양 → return
    3. answer = 최대 양 수 갱신
    4. 현재 노드를 방문 가능한 리스트(canVisit)에서 제거
    5. 현재 노드의 자식들을 canVisit에 추가
    6. canVisit 안에 있는 모든 노드(next)에 대해 dfs(next) 호출
}

재시도, 근데 또 틀림

  • 정답 알고리즘 요약만 보고 만들었는데, 또 틀림.
#include <string>
#include <vector>
#include <algorithm>
 
using namespace std;
 
vector<vector<int>> graph;
int answer = 0;
 
 
void dfs(int currentIndex, int sheep, int wolf, vector<int> canVisit, vector<int> &info)
{    
    cout << currentIndex << endl;
    if(info[currentIndex] == 0) sheep++;
    else wolf++;
    
    answer = max(answer, sheep);
    
    if(wolf >= sheep) return;
    
    canVisit.erase(find(canVisit.begin(), canVisit.end(), currentIndex));
    
    for(int i = 0; i < graph[currentIndex].size(); i++)
    {
        canVisit.push_back(graph[currentIndex][i]);
    }
    
    for(int i = 0; i < canVisit.size(); i++)
    {
        dfs(canVisit[0], sheep, wolf, canVisit, info);    
    }
}
 
int solution(vector<int> info, vector<vector<int>> edges) {
    
    vector<int> canVisit;
    
    graph.assign(info.size(), {});
    
    for(int i = 0 ; i < edges.size(); i++)
    {
        graph[edges[i][0]].push_back(edges[i][1]);
    }
    
    canVisit.push_back(0);
    
    dfs(0, 0, 0, canVisit, info);
    
    return answer;
}
  • 틀린 이유가 너무 말도 안되게 허술했음…

문제점(원인)

  1. 반복문에서 다음 방문 노드를 canVisit[0]만 사용하고 있음 → 항상 같은 노드로 재귀 호출함(타입: 논리적 버그).

    for(int i = 0; i < canVisit.size(); i++) { dfs(canVisit[0], ...); // ❌ should be canVisit[i] }

  2. 늑대 검사(wolf >= sheep)를 answer 갱신 이후에 하고 있음 → 이미 죽어야 하는(유효하지 않은) 상태를 정답으로 반영할 수 있음.
    즉, 늑대가 양 이상이면 즉시 return해야 하고 그 전에는 answer를 갱신하면 안 됨.

진짜 최종 코드

#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
 
using namespace std;
 
vector<vector<int>> graph;
int answer = 0;
 
 
void dfs(int currentIndex, int sheep, int wolf, vector<int> canVisit, vector<int> &info)
{    
    // cout << currentIndex << endl;
    if(info[currentIndex] == 0) sheep++;
    else wolf++;
    
    if(wolf >= sheep) return;
    
    answer = max(answer, sheep); 
    
    canVisit.erase(find(canVisit.begin(), canVisit.end(), currentIndex));
    
    for(int i = 0; i < graph[currentIndex].size(); i++)
    {
        canVisit.push_back(graph[currentIndex][i]);
    }
    
    for(int i = 0; i < canVisit.size(); i++)
    {
        dfs(canVisit[i], sheep, wolf, canVisit, info);    
    }
}
 
int solution(vector<int> info, vector<vector<int>> edges) {
    
    vector<int> canVisit;
    
    graph.assign(info.size(), {});
    
    for(int i = 0 ; i < edges.size(); i++)
    {
        graph[edges[i][0]].push_back(edges[i][1]);
    }
    
    canVisit.push_back(0);
    
    dfs(0, 0, 0, canVisit, info);
    
    return answer;
}

우수 코드 분석

#include <vector>
#include <algorithm>
 
using namespace std;
 
vector<vector<int>> tree;
vector<int> visited, comp;
int n, answer = 0;
 
void dfs(vector<int> cur)
{
	int sheep = 0, wolf = 0;
	for (int c : cur)
	{
		if(comp[c] == 1) wolf++;
		else sheep++;
	}
	
	if (sheep <= wolf) return;
	
	answer = max(answer, sheep);
	
	for(int i = 0; i < cur.size(); i++)
	{
		int node = cur[i];
		for(int g : tree[node])
		{
			if (visited[g]) continue;
			
			visited[g] = true;
			cur.push_back(g);
			dfs(cur);
			cur.pop_back();
			visited[g] = false;
		}
	}
}
 
int solution(vector<int> info, vector<vector<int> edge)
{
	n = info.size();
	tree.resize(n);
	visited.resize(n, false);
	comp = info;
	
	for (auto e : edges)
	{
		tree[e[0]].push_back(e[1]);
	}
	
	visited[0] = true;
	dfs({0});
	return answer;
}

그래프 뷰