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

yourjin·2022년 8월 9일

level2 알고리즘 완전탐색

알고리즘 문제풀이

목록 보기

24/28

TIL (2022.08.02)

➕ 오늘 푼 문제

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

➕ 아이디어

전력망 네트워크를 2차원 배열로 표현하고, BFS로 포함된 송전탑의 개수를 구하면 된다.

wires를 순회하며 전력망 네트워크를 2차원 배열로 표현한다.
- arr[i][j] = 1 / arr[j][i] = 1 : i와 j 송전탑이 연결되어있다.
wires의 연결을 하나씩 해제하며 bfs로 전력망의 송전탑 개수 차이를 구한다.
- 해제한 연결에 포함된 송전탑 중 하나를 start로 하여 BFS 탐색을 한다.

➕ Java 코드

import java.util.*;

class Solution {
    int[][] arr;
    
    public int bfs(int n, int start){
        int count = 1;  // start 노드부터 개수 카운트
        int[] visited =  new int[n+1];
        
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(start);
        
        while(!queue.isEmpty()){
            int v = queue.poll();
            visited[v] = 1;
            
            for(int i=1; i<=n; i++){    // 인접한 노드 방문
                if(visited[i] == 0 && arr[v][i] == 1){
                    queue.offer(i);
                    count += 1;
                }
            }
        }
        
        return Math.abs(n-count-count);
    }
    
    public int solution(int n, int[][] wires) {
        int answer = n;
        arr = new int[n+1][n+1];
        
        for(int i=0; i<wires.length; i++){
            arr[wires[i][0]][wires[i][1]] = 1;
            arr[wires[i][1]][wires[i][0]] = 1;
        }
        
        for(int i=0; i<wires.length; i++){
            // 하나씩 연결을 끊어가면서 확인
            arr[wires[i][0]][wires[i][1]] = 0;
            arr[wires[i][1]][wires[i][0]] = 0;
            
            answer = Math.min(answer, bfs(n, wires[i][0]));
            
            arr[wires[i][0]][wires[i][1]] = 1;
            arr[wires[i][1]][wires[i][0]] = 1;
        }
        
        return answer;
    }
}

➕ Python 코드

from collections import deque

def bfs(tree, n, start):
    count = 1
    visited = [False] * (n+1)
    queue = deque([start])
    
    while queue:
        v = queue.popleft()
        visited[v] = True
        
        for i in range(1, n+1):
            if not visited[i] and tree[i][v] == 1:   # v노드와 연결된 노드 중 방문하지 않은 노드들 큐에 삽입
                queue.append(i)
                count += 1
    return abs(count - (n-count))
      
def solution(n, wires):
    answer = n
    tree = [[0 for i in range(n+1)] for j in range(n+1)]
    
    for i in range(len(wires)): # 트리 만들기
        x, y = wires[i]
        tree[x][y] = 1
        tree[y][x] = 1
    
    for i in range(len(wires)): 
        x, y = wires[i] # 전선 하나씩 끊기
        tree[x][y] = 0
        tree[y][x] = 0
        
        answer = min(answer, bfs(tree, n, x))
        
        tree[x][y] = 1  # 전선 복구하기
        tree[y][x] = 1
        
    return answer