알고리즘 문제 풀이(프로그래머스 - 전력망을 둘로 나누기)

프로그래머스 LEVEL 2(전력망을 둘로 나누기)

• 사용 언어 : javascript

• 해결 날짜 : 2022-12-20

• 해결 방법 :

  • dfs를 활용해 문제 해결
    • 방문 여부와 그래프 초기화
    • 그래프 양방향 연결
    • wires를 돌며 아래를 반복
      • 현재 from에서 to로 연결된 wire 끊기
      • from으로부터 dfs
      • answer 업데이트
      • from에서 to 다시 연결
    • 이 때 dfs는 백트래킹 수행

• 회고 :

  • x

• 코드

  function solution(n, wires) {
    let answer = Infinity;
    const visited = Array.from({ length: n + 1 }, () => false);
    const graph = Array.from({ length: n + 1 }, () => Array.from({ length: n + 1 }, () => 0));
  
    for (const [from, to] of wires) {
      graph[from][to] = graph[to][from] = 1;
    }
  
    const dfs = (from) => {
      if (visited[from]) return 0;
      visited[from] = true;
      let result = 1;
  
      for (let to = 1; to <= n; to++) {
        if (!graph[from][to]) continue;
        result += dfs(to);
      }
  
      visited[from] = false;
  
      return result;
    };
  
    for (const [from, to] of wires) {
      graph[from][to] = graph[to][from] = 0;
      const count = dfs(from);
      answer = Math.min(answer, Math.abs(n - 2 * count));
      graph[from][to] = graph[to][from] = 1;
    }
  
    return answer;
  }
  

• 출처: 프로그래머스 코딩 테스트 연습, https://school.programmers.co.kr/learn/challenges