[99클럽/코딩테스트 챌린지/C++] 양과 늑대 문제 해결 과정

문제 링크:

https://school.programmers.co.kr/learn/courses/30/lessons/92343?language=cpp

프로그래머스

문제 상황

• 문제 정의: 양과 늑대가 있는 이진 트리에서, 루트 노드에서 출발하여 최대한 많은 양을 모으고 다시 루트로 돌아오는 경로를 찾아야 한다. 늑대 수가 양 수 이상이 되는 순간 모든 양이 잡아먹히므로, 늑대 수를 양보다 적게 유지하면서 탐색을 진행해야 한다.

---

문제 원인

1. 양방향 간선의 특성:
   • 그래프가 양방향으로 연결되어 있어, 동일한 노드를 여러 경로로 방문할 가능성이 있었다.
   • 단순히 노드 방문 여부만 체크하면 동일한 상태로 무한 루프에 빠질 수 있었다.
2. 상태 기반 탐색 필요성:
   • 양방향 그래프에서는 방문 여부 외에도 **현재 상태(모은 양과 늑대의 수)**를 기준으로 탐색을 관리해야 한다.
   • 동일한 노드라도 상태가 다르면 다시 방문해야 하는 상황이 발생했다.

---

해결 방법

1. 3차원 배열로 상태 관리:
   • (노드 번호, 양의 수, 늑대의 수)를 기준으로 방문 여부를 체크하는 3차원 배열을 사용하여 상태를 중복 관리하지 않도록 설계.
   • visit[node][sheep][wolf] 배열로 현재 상태를 기록.
2. DFS를 활용한 완전 탐색:
   • 현재 노드에서 방문 가능한 자식 노드를 탐색하며, 조건에 따라 상태를 갱신.
   • 늑대 수가 양 수 이상이 되는 상태에서는 탐색을 중단.
3. 상태 복구:
   • 탐색 종료 후 visit 배열과 노드 상태(state)를 복구하여 다른 경로 탐색에 영향을 주지 않도록 처리.

---

최종 코드

#include <algorithm>
#include <iostream>
#include <vector>
#include <tuple>

#define MAX 20

using namespace std;

vector<int> node[MAX]; // 그래프를 저장하는 배열 (인접 리스트)
vector<int> state;     // 각 노드의 상태 (0: 양, 1: 늑대, -1: 방문 처리)
int maxSheep;          // 모을 수 있는 최대 양 수
bool visit[MAX][MAX][MAX]; // 방문 상태 저장 [노드][양 수][늑대 수]

// 간선 정보를 바탕으로 그래프를 생성하는 함수
void makeConnection(vector<vector<int>> edges) {
    for (auto n : edges) {
        node[n[0]].push_back(n[1]); // 양방향 간선 추가
        node[n[1]].push_back(n[0]);
    }
}

// DFS 탐색 함수
void dfs(int cur, int sheep, int wolf) {
    // 루트 노드(0)로 돌아온 경우 최대 양 수 갱신
    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);             // 양 1마리 증가, DFS 재귀 호출
                visit[next][sheep + 1][wolf] = false;   // 방문 상태 복구
                state[next] = 0;                        // 원래 상태 복구
            }
        }
        // 다음 노드가 늑대인 경우
        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);             // 늑대 1마리 증가, DFS 재귀 호출
                visit[next][sheep][wolf + 1] = false;   // 방문 상태 복구
                state[next] = 1;                        // 원래 상태 복구
            }
        }
        // 다음 노드가 이미 방문된 경우
        else {
            if (visit[next][sheep][wolf] == false) {
                visit[next][sheep][wolf] = true;        // 현재 상태 방문 처리
                dfs(next, sheep, wolf);                // 상태 유지, DFS 재귀 호출
                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; // 루트 노드 초기 상태 방문 처리 (양 1, 늑대 0)
    dfs(0, 1, 0);          // DFS 시작
    return maxSheep;       // 최대 양 수 반환
}

---

배운 점

1. 양방향 그래프의 탐색
   • 양방향 그래프에서 단순 방문 체크만으로는 모든 경로를 탐색할 수 없다.
   • 방문 상태와 함께 **탐색 상태(양과 늑대의 수)**를 함께 관리해야 한다..
2. 3차원 배열의 활용
   • 문제의 조건에 따라 다차원 배열을 사용하여 상태를 관리하는 방법을 학습.
   • 노드와 상태를 조합하여 중복 탐색을 방지했다.
3. DFS와 상태 복구
   • DFS에서 상태를 변경한 후, 재귀 호출이 끝나면 반드시 원래 상태로 복구해야 한다는 것을 확인.

---

결론

• 이 문제는 단순히 노드를 탐색하는 것이 아니라, 상태 기반으로 조건을 만족하며 탐색해야 하는 전형적인 DFS 문제였다.
• 3차원 배열을 활용하여 상태를 관리함으로써, 양방향 그래프에서의 중복 탐색 문제를 해결할 수 있었다.
• 탐색 상태를 관리하고 복구하는 과정은 모든 DFS/백트래킹 문제에서 중요한 패턴이라는 것을 다시 한 번 깨달았다.