[PCCP] Lv3: 양과 늑대(92343) 해설

문제

- 문제 링크: 양과 늑대

 

코드

(C언어)

solution 1)

#include<>

solution 2)

#include<>

 

(C++)

solution 1)

- N: info의 길이

- edges 벡터를 순회하면서 트리를 생성하는 동작의 시간 복잡도는 O(N)

- 이후 너비우선탐색을 할 때의 시간 복잡도는 O(N^2)

- 최종 시간 복잡도: O(N^2)

#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>> edges) {
    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;
}

solution 2)

#include<>

 

(C#)

solution 1)

#include<>

solution 2)

#include<>

 

(Java)

solution 1)

- N: info의 길이

- edges 배열을 순회하면서 트리를 생성하는 동작의 시간 복잡도는 O(N)

- 이후 너비우선탐색을 할 때의 시간복잡도는 O(N^2)

- 최종 시간 복잡도: O(N^2)

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.HashSet;

public class Solution {

    // 현재 위치, 양의 수, 늑대의 수 방문한 노드 저장을 위한 클래스
    private static class Info {
        int node, sheep, wolf;
        HashSet<Integer> visited;

        public Info(int node, int sheep, int wolf, HashSet<Integer> visited) {
            this.node = node;
            this.sheep = sheep;
            this.wolf = wolf;
            this.visited = visited;
        }
    }

    private static ArrayList<Integer>[] tree; // 트리 정보를 저장할 인접리스트

    // 트리 구축 메소드
    private static void buildTree(int[] info, int[][] edges) {
        tree = new ArrayList[info.length];
        for (int i = 0; i < tree.length; i++) {
            tree[i] = new ArrayList<>();
        }

        for (int[] edge : edges) {
            tree[edge[0]].add(edge[1]);
        }
    }

    public int solution(int[] info, int[][] edges) {
        buildTree(info, edges); // 트리 생성

        int answer = 0; // 최대 양의 수를 저장할 변수

        // BFS를 위한 큐 생성 및 초기 상태 설정
        ArrayDeque<Info> queue = new ArrayDeque<>();
        queue.add(new Info(0, 1, 0, new HashSet<>()));

        // BFS(너비 우선 탐색) 시작
        while (!queue.isEmpty()) {
            // 큐에서 현재 상태를 꺼냄
            Info now = queue.poll();
            // 최대 양의 수 업데이트
            answer = Math.max(answer, now.sheep);
            // 방문한 노드 집합에 현재 노드의 이웃 노드 추가
            now.visited.addAll(tree[now.node]);

            // 인접한 노드들에 대해 탐색
            for (int next : now.visited) {
                // 기존 해시셋의 데이터를 복사하고 현재 방문한 정점을 해시셋에서 제거
                HashSet<Integer> set = new HashSet<>(now.visited);
                set.remove(next);

                if (info[next] == 1) { // 늑대일 경우
                    if (now.sheep != now.wolf + 1) {
                        queue.add(new Info(next, now.sheep, now.wolf + 1, set));
                    }
                }
                else { // 양일 경우
                    queue.add(new Info(next, now.sheep + 1, now.wolf, set));
                }
            }
        }

        return answer;
    }

}

solution 2)

#include<>

 

(Python)

solution 1)

- N: info의 길이

- edges 리스트를 순회하면서 트리를 생성하는 동작의 시간 복잡도: O(N)

- 너비 우선 탐색을 할 때 시간 복잡도: O(N^2)

- 최종 시간 복잡도: O(N^2)

from collections import deque

def solution(info, edges):
    # 트리 구축 함수
    def build_tree(info, edges):
        tree = [[] for _ in range(len(info))]
        for edge in edges:
            tree[edge[0]].append(edge[1])
        return tree
        
    tree = build_tree(info, edges) # 트리 생성
    max_sheep = 0 # 최대 양의 수를 저장할 변수 초기화
    
    # BFS를 위한 큐 생성 및 초기 상태 설정
    # (현재 위치, 양의 수, 늑대의 수, 방문한 노드 집합)
    q = deque([(0, 1, 0, set())])
    
    # BFS 시작
    while q:
        # 큐에서 상태 가져오기
        current, sheep_count, wolf_count, visited = q.popleft()
        # 최대 양의 수 업데이트
        max_sheep = max(max_sheep, sheep_count)
        # 방문한 노드 집합에 현재 노드의 이웃 노드 추가
        visited.update(tree[current])
        
        # 인접한 노드들에 대해 탐색
        for next_node in visited:
            if info[next_node]:  # 늑대일 경우
                if sheep_count != wolf_count + 1:
                    q.append(
                        (next_node, sheep_count, wolf_count + 1, visited - {next_node})
                    )
            else:  # 양일 경우
                q.append(
                    (next_node, sheep_count + 1, wolf_count, visited - {next_node})
                )
    return max_sheep

solution 2)

import

 

(JavaScript)

solution 1)

- N: info의 길이

- edges 배열을 순회하면서 트리를 생성하는 동작: O(N)

- 너비 우선 탐색: O(N^2)

- 최종 시간복잡도: O(N^2)

class Queue {
    items = [];
    front = 0;
    rear = 0;
    
    push(item) {
        this.items.push(item);
        this.rear++;
    }
    
    pop() {
        return this.items[this.front++];
    }
    
    isEmpty() {
        return this.front === this.rear;
    }
}

// 트리 구축 함수
function buildTree(info, edges) {
    const tree = Array.from({length: info.length}, () => []);
    
    for (const [from, to] of edges) {
        tree[from].push(to);
    }
    
    return tree;
}

function solution(info, edges) {
    const tree = buildTree(info, edges); // 트리 생성
    let maxSheep = 0; // 최대 양의 수를 저장할 변수 초기화
    
    // BFS를 위한 큐 생성 및 초기 상태 설정
    const q = new Queue();
    q.push([0, 1, 0, new Set()]); // (현재 위치, 양의 수, 늑대의 수, 방문한 노드 집합)
    
    //BFS 시작
    while (!q.isEmpty()) {
        // 큐에서 상태 가져오기
        const [current, sheepCount, wolfCount, visited] = q.pop();
        // 최대 양의 수 업데이트
        maxSheep = Math.max(maxSheep, sheepCount);
        // 방문한 노드 집합에 현재 노드의 이웃 노드 추가
        for (const next of tree[current]) {
            visited.add(next);
        }
        // 인접한 노드들에 대해 탐색
        for (const next of visited) {
           if (info[next]) { // 늑대일 경우
             if (sheepCount !== wolfCount + 1) {
                 const newVisited = new Set(visited);
                 newVisited.delete(next);
                 q.push([next, sheepCount, wolfCount + 1, newVisited]);
             }
           } else {
               const newVisited = new Set(visited);
               newVisited.delete(next);
               q.push([next, sheepCount + 1, wolfCount, newVisited]);
           }
        }
    }
    
    return maxSheep;
}

solution 2)

import