[99클럽 코테 스터디 2일차 TIL] BFS

📖 오늘의 학습 키워드
BFS

오늘의 회고

문제

[전력망을 둘로 나누기]
https://school.programmers.co.kr/learn/courses/30/lessons/86971

나의 해결

import java.util.*;
class Solution {
    public boolean[] visitedTower;
    public int answer, len;
    public int solution(int n, int[][] wires) {
        answer = n;
        len = wires.length;
        for(int i = 0; i < len; i++) {
            visitedTower = new boolean[n+1];
            bfs(i, n, wires);
        }
        return answer;
    }
    public void bfs(int idx, int n, int[][] wires) {
        Queue<Integer> q = new LinkedList<>();
        int count = 1;
        int start = wires[idx][0];
        q.add(start);
        visitedTower[start] = true;
        while(!q.isEmpty()){
            int now = q.poll();
            for(int i = 0; i < len; i++){
                if(i != idx){
                    if(wires[i][0] == now && !visitedTower[wires[i][1]]) {
                        q.add(wires[i][1]);
                        visitedTower[wires[i][1]] = true;
                        count++;
                    }
                    if(wires[i][1] == now && !visitedTower[wires[i][0]]) {
                        q.add(wires[i][0]);
                        visitedTower[wires[i][0]] = true;
                        count++;
                    }
                }
            }
        }
        answer = Math.min(answer, Math.abs(count-(n-count)));
    }
}

모든 전선을 한 번씩 끊어보며 두 전력망이 가지고 있는 송전탑 개수의 차이(절댓값)의 최솟값을 구한다. 송전탑이 트리 형태로 연결되어 있기 때문에 하나의 전선만 끊으면 무조건 두 개의 전력망으로 나뉠 수 있다.

한 전력망에 속하는 송전탑의 개수는 BFS를 이용해 구했다. 탐색 시작 노드는 끊어진 전선에서 처음 원소 즉 문제에서의 v1번 송전탑으로 지정한다. 그 뒤 v1 송전탑과 연결된 다른 송전탑의 개수를 구한다. 그리고 이를 전체 송전탑의 개수 n에서 빼 나머지 한쪽의 개수를 구하고 최종적으로 이 둘의 차이를 구해 최솟값을 갱신한다.

새로 학습한 내용

처음에 풀 때는 착각해서 전선 정보에 대해서도 방문 여부를 확인하는 코드를 작성하였다. 물론 이 코드를 포함하고 제출했을 때도 통과하기는 했지만 분명 두 코드의 실행시간에는 유의미한 차이가 있었다. 앞으로는 불필요한 연산을 하지 않도록 항상 유의해야겠다는 생각이 들었다.