[프로그래머스] 전력망을 둘로 나누기 [Python(파이썬), Java(자바)]

문제

https://programmers.co.kr/learn/courses/30/lessons/86971

코딩테스트 연습 - 9주차_전력망을 둘로 나누기

 

풀이

브루트포스 + 그래프 탐색을 이용해 풀 수 있는 문제였다. 기본 문제풀이 로직은 다음과 같다.

1. for문을 통해 그래프의 간선을 하나씩 제외한다.
2. 나머지 간선들로 그래프를 초기화한다.
3. 간선이 n-2개 존재할 시 그래프는 2분할되므로 각 영역에 속한 노드 수의 차를 구하고 answer을 갱신한다.

중요한 점은 그래프가 트리 구조로 되어있다는 것이다. 따라서 간선은 무조건 n-1개 존재하며, n-2개 존재할 시엔 그래프가 2분할이 된다.

 

코드

파이썬

import sys
from collections import defaultdict
sys.setrecursionlimit(10**6)

def solution(n, wires):
    answer = float('inf')

    def dfs(cur, cnt):
        visited[cur] = 1
        cnt += 1
        for adj in g[cur]:
            if not visited[adj]:
                cnt = dfs(adj, cnt)
        return cnt   

    # init graph
    for i in range(n-1):
        g = defaultdict(list)

        for idx, wire in enumerate(wires):
            if idx == i:
                continue
            g[wire[0]].append(wire[1])
            g[wire[1]].append(wire[0])

        # travel graph
        visited = [0 for _ in range(n+1)]
        area = []

        for node in range(1, n+1):
            if not visited[node]:
                area.append(dfs(node, 0))

        answer = min(answer, abs(area[0] - area[1]))

    return answer

자바

import java.util.ArrayList;
import java.util.List;

class Solution {
    static List<Integer>[] graph;
    static boolean[] visited;

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

        for(int i=0; i<n-1; i++) {
            // init graph
            graph = new ArrayList[n+1];

            for(int j=1; j<n+1; j++) {
                graph[j] = new ArrayList<>();
            }

            for(int k=0; k<n-1; k++) {
                if (i==k) {
                    continue;
                }
                graph[wires[k][0]].add(wires[k][1]);
                graph[wires[k][1]].add(wires[k][0]);
            }

            // travel graph
            visited = new boolean[n+1];
            List<Integer> area = new ArrayList<>();

            for(int node=1; node<n+1; node++) {
                if (!visited[node]) {
                    area.add(dfs(node, 0));
                }
            }

            answer = Math.min(answer, Math.abs(area.get(0) - area.get(1)));
        }

        return answer;
    }

    public int dfs(int cur, int cnt) {
        visited[cur] = true;
        cnt++;

        for(int adj:graph[cur]) {
            if (!visited[adj]) {
                cnt = dfs(adj, cnt);
            }
        }

        return cnt;
    }
}