프로그래머스 lv2 전력망을 둘로 나누기

문제링크

전력망을 둘로 나누기

풀이

• 선을 끊고, 이걸로 bfs를 하면 되겠거니 생각은 했으나, 늘 생각은 하고 구현은 못한다.
• 앞선 선을 끊는다를 어떻게 해야할 지 몰랐으니, 어쩔 수 없이 또 찾아보고 진행했다.
• 인접 행렬을 구현해주고, 그에 맞춰서 선을 끊는 부분을 0으로 바꿔주면 되는 것이었다.
• 마지막에 끊은 배열의 왼쪽과 연결되어있는 간선 개수 (cnt) 와 오른쪽과 연결되어있는 간선 개수 (n - cnt) 개수를 빼주고 절대값을 구해주면 된다.

import java.util.LinkedList;
import java.util.Queue;

class Solution {
  int[][] arr;
  
  public int solution(int n, int[][] wires) {
      int answer = Integer.MAX_VALUE;

      // 인접 행렬을 만들고,
      arr = new int[n + 1][n + 1];
      for (int[] wire : wires) {
          arr[wire[0]][wire[1]] = 1;
          arr[wire[1]][wire[0]] = 1;
      }

      for (int[] wire : wires) {
          // 선을 차례대로 끊으면서
          arr[wire[0]][wire[1]] = 0;
          arr[wire[1]][wire[0]] = 0;

          // bfs로 탐색한다.
          answer = Math.min(answer, bfs(wire[0], n));

          // 탐색이 끝나면 선은 복구한다.
          arr[wire[0]][wire[1]] = 1;
          arr[wire[1]][wire[0]] = 1;
      }

      return answer;
  }

  // 왼쪽의 숫자를 기준으로 탐색
  public int bfs(int left, int n) {
      int cnt = 1;
      boolean[] visited = new boolean[n + 1];
      Queue<Integer> queue = new LinkedList<>();
      queue.add(left);

      while (!queue.isEmpty()) {
          int tmp = queue.poll();
          visited[tmp] = true;
          for (int i = 1; i < n + 1; i++) {
              if (arr[tmp][i] == 1 && !visited[i]) {
                  queue.add(i);
                  cnt++;
              }
          }
      }
      
      // cnt = 왼쪽이 연결된 전선망 개수
      // n - cnt = 오른쪽이 연결된 전선망 개수
      // 최종 리턴 값 : n - cnt - cnt 의 절대값
      
      return Math.abs(n - (2 * cnt));
  }
}

소감

• 인접행렬로 구하는건 처음 해보았다.
• bfs, dfs에 대해서 여전히 머릿속에서는 계산이 되지 않는중