Programmers 양과 늑대

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

프로그래머스

 

 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int maxSheep = 0; // 최대 양의 수를 저장하는 전역 변수

// DFS를 이용한 트리 탐색 함수
void DFS(int node, int sheep, int wolf, vector<bool>& visited,
         vector<int>& info, vector<vector<int>>& graph, vector<int>& possible) 
{
    // 현재 노드가 양이면 sheep++, 늑대면 wolf++
    if (info[node] == 0) sheep++;
    else wolf++;

    // 늑대의 수가 양의 수 이상이 되면 탐색 종료
    if (wolf >= sheep) return;

    // 최대 양의 수 갱신
    maxSheep = max(maxSheep, sheep);

    // 현재 노드에서 갈 수 있는 노드 목록 업데이트
    vector<int> next_possible = possible;
    for (int next : graph[node]) 
    {
        if (!visited[next]) next_possible.push_back(next);
    }

    // 다음 가능한 노드들을 탐색
    for (int next : next_possible) 
    {
        if (!visited[next]) 
        {
            visited[next] = true; // 방문 처리
            DFS(next, sheep, wolf, visited, info, graph, next_possible);
            visited[next] = false; // 방문 복원 (백트래킹)
        }
    }
}

// 트리 구조에서 최대 양의 수를 계산하는 함수
int solution(vector<int> info, vector<vector<int>> edges) 
{
    int n = info.size(); // 노드의 수
    vector<vector<int>> graph(n); // 트리를 나타내는 인접 리스트
    vector<bool> visited(n, false); // 노드 방문 여부를 저장
    vector<int> possible; // 탐색 가능한 노드 목록

    // 간선 정보를 이용해 그래프 생성
    for (auto& edge : edges) 
    {
        graph[edge[0]].push_back(edge[1]);
    }

    visited[0] = true; // 루트 노드(0번 노드)부터 탐색 시작
    DFS(0, 0, 0, visited, info, graph, possible);

    return maxSheep; // 최대 양의 수 반환
}

int main() 
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int n; // 노드 수 입력
    cin >> n;

    // 노드 정보 입력 (0: 양, 1: 늑대)
    vector<int> info(n);
    for (int i = 0; i < n; i++) 
    {
        cin >> info[i];
    }

    // 간선 정보 입력
    vector<vector<int>> edges;
    for (int i = 0; i < n - 1; i++) 
    {
        int parent, child;
        cin >> parent >> child;
        edges.push_back({ parent, child });
    }

    // 최대 양의 수 계산
    int maxSheep = solution(info, edges);
    cout << maxSheep << endl; // 결과 출력

    return 0;
}

 

 

처음엔 vector대신 pair를 사용했는데..틀리다고 나와서 vector로 바꿨다

 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int maxSheep = 0;

void DFS(int node, int sheep, int wolf, vector<bool>& visited,
    vector<int>& info, vector<vector<int>>& graph, vector<int>& possible) 
    {
    if (info[node] == 0) sheep++;
    else wolf++;

    if (wolf >= sheep) return;
    maxSheep = max(maxSheep, sheep);

    vector<int> next_possible = possible;
    for (int next : graph[node]) 
    {
        if (!visited[next]) next_possible.push_back(next);
    }

    for (int next : next_possible) 
    {
        if (!visited[next]) 
        {
            visited[next] = true;
            DFS(next, sheep, wolf, visited, info, graph, next_possible);
            visited[next] = false;
        }
    }
}

int solution(vector<int> info, vector<pair<int, int>> edges) 
{
    int n = info.size();
    vector<vector<int>> graph(n);
    vector<bool> visited(n, false);
    vector<int> possible;

    for (auto& edge : edges) 
    {
        graph[edge.first].push_back(edge.second);
    }

    visited[0] = true;
    DFS(0, 0, 0, visited, info, graph, possible);

    return maxSheep;
}

int main() 
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int n; // 노드 수 입력
    cin >> n;

    // 노드 정보 (0: 양, 1: 늑대)
    vector<int> info(n);
    for (int i = 0; i < n; i++) 
    {
        cin >> info[i];
    }

    // 간선 정보 입력
    vector<pair<int, int>> edges;
    for (int i = 0; i < n - 1; i++) 
    {
        int parent, child;
        cin >> parent >> child;
        edges.push_back({ parent, child });
    }

    // solution 함수 호출
    int maxSheep = solution(info, edges);
    cout << maxSheep << endl;

    return 0;
}

 

gpt에게 물어보니 결과는 동일한 것 같다

시간 복잡도 분석

공통 요소의 시간 복잡도

1. 그래프 생성 시간
   • 두 코드 모두 solution 함수에서 간선 정보를 기반으로 인접 리스트 graph를 생성합니다.
   • 그래프 생성은 입력된 edges를 순회하며 수행되므로 시간 복잡도는 O(E)O(E)O(E)입니다. 여기서 EEE는 간선의 수로, 트리의 경우 항상 E=N−1E = N - 1E=N−1입니다.
2. DFS 탐색 시간
   • DFS는 모든 노드를 한 번씩 방문하고, 각 노드의 인접 노드를 탐색합니다.
   • 따라서 DFS의 시간 복잡도는 O(V+E)O(V + E)O(V+E)입니다. 트리에서는 E=V−1E = V - 1E=V−1이므로 결과적으로 O(V+V−1)=O(2V−1)=O(V)O(V + V - 1) = O(2V - 1) = O(V)O(V+V−1)=O(2V−1)=O(V)입니다. VVV는 노드의 수입니다.

차이점에 따른 시간 복잡도

1. 첫 번째 코드 (vector<pair<int, int>> 사용)
   • 간선을 저장하는 vector<pair<int, int>>는 선형적으로 순회하면서 그래프를 생성합니다.
   • 간선 정보는 O(E)O(E)O(E)의 시간에 접근 가능하며, graph를 구성하는 데도 O(E)O(E)O(E)가 소요됩니다.
   • 총 시간 복잡도는 그래프 생성 O(E)O(E)O(E) + DFS O(V)O(V)O(V) = O(V)O(V)O(V).
2. 두 번째 코드 (vector<vector<int>> 사용)
   • 간선 정보를 저장하면서 vector<vector<int>>에 직접 추가됩니다.
   • 간선 정보의 크기 접근은 O(1)O(1)O(1), 그래프 생성도 O(E)O(E)O(E)입니다.
   • DFS 역시 O(V)O(V)O(V)입니다.
   • 총 시간 복잡도는 첫 번째 코드와 동일한 O(V)O(V)O(V)입니다.

결론: 시간 복잡도

두 코드의 시간 복잡도는 동일하며, O(V)O(V)O(V)입니다.