[PS] 99클럽 코테 스터디 36일차 TIL (전력망을 둘로 나누기)

문제

문제 링크

설명

최초 그래프 간선 정보가 주어지고, 해당 그래프에서 간선을 하나씩 끊었을 때 두 부분으로 나누어지는 그래프의 노드 수 차이가 최소가 되도록 하는 문제

풀이

위 예시를 인접 행렬 그래프로 나타내면 아래와 같다.

1. graph 선언 : 정점과 간선 정보가 주어지므로 해당 좌표를 양방향 연결하기 위해 int[][] 로 graph 를 선언해줬다. boolean[][] 로 선언해도 상관없다.

2. graph 세팅 : 양방향 연결을 위해 다음과 같이 그래프 초기 세팅을 진행한다.

   graph[wire[0]][wire[1]] = 1;
   graph[wire[1]][wire[0]] = 1;
   

3. 간선 끊기 : 다음과 같이 간선을 하나씩 끊었을 때의 노드 수를 센다.

   // 간선을 끊고
   graph[u][v] = 0;
   graph[v][u] = 0;
   // 그 그래프를 dfs 돌린다. 문제에서 n 은 자연수라고 했으므로 graph 는 1부터 세팅되어 있다.
   dfs(1, visited, graph);
   

4. 노드 수 차이가 최소가 되는 값 찾기 : dfs 에서 찾은 한 그래프의 노드 수가 count 라면, 나머지 그래프의 노드 수는 n - count 가 된다. 이 두 수의 차이를 구하고 기존의 최소값 보다 작은 경우 minDiff 를 갱신해 나간다.
5. 간선 복구 : 끊었던 간선을 다시 연결시켜 주고, 다음 wire 에 대해 탐색한다.

class Solution {
  static int[][] graph;
  static boolean[] visited;

  public int solution(int n, int[][] wires) {
    graph = new int[n + 1][n + 1];

    for (int[] wire : wires) {
      graph[wire[0]][wire[1]] = 1;
      graph[wire[1]][wire[0]] = 1;
    }

    int minDiff = Integer.MAX_VALUE;

    for (int[] wire : wires) {
      int u = wire[0];
      int v = wire[1];

      graph[u][v] = 0;
      graph[v][u] = 0;

      visited = new boolean[n + 1];
      int count1 = dfs(1, visited, graph);
      int count2 = n - count1;

      int diff = Math.abs(count1 - count2);
      minDiff = Math.min(minDiff, diff);

      graph[u][v] = 1;
      graph[v][u] = 1;
    }
    return minDiff;
  }

  private int dfs(int node, boolean[] visited, int[][] graph) {
    visited[node] = true;
    int count = 1;

    for (int i = 1; i < graph.length; i++) {
      if (!visited[i] && graph[node][i] == 1) {
        count += dfs(i, visited, graph);
      }
    }
    return count;
  }
}