[PCCP] Lv2: 전력망을 둘로 나누기(86971) 해설

문제

- 문제 링크: 전력망을 둘로 나누기

 

해설

- 자료구조: 

- 시간복잡도: 

 

(풀이과정)

1) 

2) 

3) 

4) 

 

코드

(C언어)

solution 1)

solution 1

#include<>

solution 2)

#include<>

solution 3)

#include<>

 

(C++)

solution 1)

#include<>

solution 2)

#include<>

solution 3)

#include<>

 

(C#)

solution 1)

#include<>

solution 2)

#include<>

solution 3)

#include<>

 

(Java)

solution 1)

- N은 송전탑의 개수

- 깊이우선탐색을 이용하여 한 번에 탑을 구하므로 시간 복잡도는 O(N)

- N이 100이하이므로 O(N^2)으로 풀이 가능

import java.util.ArrayList;

public class Solution {

    private static boolean[] visited;
    private static ArrayList<Integer>[] adjList;
    private static int N, answer;

    public static int solution(int n, int[][] wires) {
        N = n;
        answer = n - 1;

        // 전선의 연결 정보를 저장할 인접 리스트 초기화
        adjList = new ArrayList[n + 1];
        for (int i = 1; i <= n; i++) {
            adjList[i] = new ArrayList<>();
        }

        // 전선의 연결 정보를 인접 리스트에 저장
        for (int[] wire : wires) {
            adjList[wire[0]].add(wire[1]);
            adjList[wire[1]].add(wire[0]);
        }

        visited = new boolean[n + 1];

        // 깊이 우선 탐색 시작
        dfs(1);

        return answer;
    }

    private static int dfs(int now) {
        visited[now] = true;

        // 자식 노드의 수를 저장하고 반환할 변수 선언
        int sum = 0;
        // 연결된 모든 전선을 확인
        for (int next : adjList[now]) {
            if (!visited[next]) {
                // (전체 노드 - 자식 트리의 노드 수) - (자식 트리의 노드 수) 의 절대값이 가장 작은 값을 구함
                int cnt = dfs(next); // 자식 트리가 가진 노드의 수
                answer = Math.min(answer, Math.abs(N - cnt * 2));
                // 자식 노드의 수를 더함
                sum += cnt;
            }
        }

        // 전체 자식 노드의 수에 1(현재 now 노드)을 더해서 반환
        return sum + 1;
    }

}

solution 2)

#include<>

solution 3)

#include<>

 

(Python)

solution 1)

- N: 송전탑의 개수

- 깊이 우선 탐색을 한 번 할 때마다 시간복잡도는 O(N)이고 이를 N번 진행하므로 최종 시간 복잡도는 O(N^2)

def solution(n, wires):
    # 그래프 생성
    graph = [[] for _ in range(n + 1)]
    for a, b in wires:
        graph[a].append(b)
        graph[b].append(a)
        
    # 깊이 우선 탐색 함수
    def dfs(node, parent):
        cnt = 1
        for child in graph[node]: # 현재 노드의 자식 노드들에 방문
            if child != parent: # 부모 노드가 아닌 경우에만 탐색
                cnt += dfs(child, node)
        return cnt
        
    min_diff = float("inf")
    for a, b in wires:
        # 간선제거
        graph[a].remove(b)
        graph[b].remove(a)
        
        # 각 전력망 송전탑 개수 계산
        cnt_a = dfs(a, b)
        cnt_b = n - cnt_a
        
        # 최솟값 갱신
        min_diff = min(min_diff, abs(cnt_a - cnt_b))
        
        # 간선 복원
        graph[a].append(b)
        graph[b].append(a)
        
    return min_diff

solution 2)

import

solution 3)

import

 

(JavaScript)

solution 1)

- N: 송전탑의 개수

- 깊이 우선 탐색을 한 번할 때마다 시간복잡도는 O(N)이고 이를 N번 진행

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

function solution(n, wires) {
    // 그래프 생성
    const graph = Array.from({length: n + 1}, () => []);
    for (const [a, b] of wires) {
        graph[a].push(b);
        graph[b].push(a);
    }
    
    // 깊이 우선 탐색 함수
    function dfs(node, parent) {
        let cnt = 1;
        for (const child of graph[node]) { // 현재 노드의 자식 노드들에 방문
            if (child !== parent) { // 부모 노드가 아닌 경우에만 탐색
                cnt += dfs(child, node);
            }
        }
        return cnt;
    }
    
    let minDiff = Infinity;
    for (const [a, b] of wires) {
        // 간선 제거
        graph[a].splice(graph[a].indexOf(b), 1);
        graph[b].splice(graph[b].indexOf(a), 1);
        
        // 각 전력망 송전탑 개수 계산
        const cntA = dfs(a, b);
        const cntB = n - cntA;
        
        // 최솟값 갱신
        minDiff = Math.min(minDiff, Math.abs(cntA - cntB));
        
        // 간선 복원
        graph[a].push(b);
        graph[b].push(a);
    }
    
    return minDiff;
}

solution 2)

import

solution 3)

import