[Programmers] 전력망을 둘로 나누기 ( Stack, DFS )

 

- 목차

 

문제 설명.

n개의 송전탑이 전선을 통해 하나의 트리 형태로 연결되어 있습니다. 당신은 이 전선들 중 하나를 끊어서 현재의 전력망 네트워크를 2개로 분할하려고 합니다. 이때, 두 전력망이 갖게 되는 송전탑의 개수를 최대한 비슷하게 맞추고자 합니다.

송전탑의 개수 n, 그리고 전선 정보 wires가 매개변수로 주어집니다. 전선들 중 하나를 끊어서 송전탑 개수가 가능한 비슷하도록 두 전력망으로 나누었을 때, 두 전력망이 가지고 있는 송전탑 개수의 차이(절대값)를 return 하도록 solution 함수를 완성해주세요.

---

제한사항

• n은 2 이상 100 이하인 자연수입니다.
• wires는 길이가 n-1인 정수형 2차원 배열입니다.
  • wires의 각 원소는 [v1, v2] 2개의 자연수로 이루어져 있으며, 이는 전력망의 v1번 송전탑과 v2번 송전탑이 전선으로 연결되어 있다는 것을 의미합니다.
  • 1 ≤ v1 < v2 ≤ n 입니다.
  • 전력망 네트워크가 하나의 트리 형태가 아닌 경우는 입력으로 주어지지 않습니다

 

 

문제 분석.

둘로 나눈 트리를 탐색합니다.

TreeA, TreeB 로 분리되었다고 하였을 때에 Tree A 를 탐색한 노드의 수와 Tree B 를 탐색한 노드의 수의 차를 최소화시키는 것이

이 문제의 핵심입니다.

전체 노드의 수는 N 으로 고정되어 있으므로 의도적으로 분리시킨 Tree A 를 탐색한 노드 갯수만을 구하면 됩니다.

 

Tree Node : N

Tree A Node : M

Tree B Node : N - M

 

트리의 전체 노드를 탐색하기 위해서 Stack 과 DFS 를 사용하였습니다.

 

문제 풀이.

import java.util.*;


class Solution {
  public int solution(int n, int[][] wires) {
    int answer = Integer.MAX_VALUE;
    List<Integer>[] graph = new ArrayList[n + 1];

    for (int i = 0; i < wires.length; i++) {
      int source = wires[i][0];
      int dest = wires[i][1];
      if (graph[source] == null) graph[source] = new ArrayList<>();
      if (graph[dest] == null) graph[dest] = new ArrayList<>();

      graph[source].add(dest);
      graph[dest].add(source);
    }

    for (int i = 0; i < wires.length; i++) {
      int source = wires[i][0];
      int dest = wires[i][1];
      int nextSource = wires[((i + 1) % wires.length)][0];
      int eachTry = findPath(nextSource, graph, new int[]{source, dest});
      int diff = Math.abs((n - eachTry) - eachTry);
      answer = Math.min(answer, diff);
    }
    return answer;
  }

  int findPath(int source, List<Integer>[] graph, int[] disabledPath) {
    int nodeCount = 1;
    boolean[] visited = new boolean[graph.length];
    Stack<Integer> stack = new Stack();
    stack.add(source);
    visited[source] = true;
    while (!stack.isEmpty()) {
      int node = stack.pop();
      for (int dest : graph[node]) {
        if (visited[dest]) continue;
        if (disabledPath[0] == node && disabledPath[1] == dest) continue;
        if (disabledPath[1] == node && disabledPath[0] == dest) continue;
        stack.add(dest);
        nodeCount++;
        visited[dest] = true;
      }
    }
    return nodeCount;
  }
}