[프로그래머스 / Java] 코딩테스트 연습: 전력망을 둘로 나누기 (완전탐색)

난이도: Level 2

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

프로그래머스

---

 

우선 전역에서 사용할 변수로 트리(리스트 배열)를 선언한다.

 

    class Solution {

        List<Integer>[] tree;   // 트리 리스트 배열

 

 

solution 메서드 안에 변수를 다음과 같이 선언한다.

최솟값을 구해야 하므로 answer 변수의 초깃값은 최댓값으로 설정한다.

n번 송전탑도 인덱스에 포함되어야 하므로 tree 배열의 크기를 n + 1로 선언한다.

 

    int answer = Integer.MAX_VALUE; // 두 전력망이 가지고 있는 송전탑 개수의 차이(절대값)의 최솟값

    tree = new ArrayList[n + 1];    // 트리 리스트의 배열이 인덱스를 n까지 가질 수 있도록 초기화

 

 

1번 송전탑과 연결된 송전탑들을 여러개 저장하기 위해 ArrayList를 가질 수 있도록 초기화하고,

2번 송전탑과 연결된 송전탑들을 여러개 저장하기 위해 ArrayList를 가질 수 있도록 초기화하고,

...

2번 송전탑과 연결된 송전탑들을 여러개 저장하기 위해 ArrayList를 가질 수 있도록 초기화한다.

 

    // 각 송전탑(1부터 n까지)이 모두 ArrayList를 가질 수 있도록 초기화

    for (int i = 1; i <= n; i++) {

        tree[i] = new ArrayList<>();

    }

 

 

문제에 주어진 모든 전선을 양방향 연결한다.

 

    // 모든 전선 연결

    for (int[] wire : wires) {

        int v1 = wire[0];   // v1 송전탑

        int v2 = wire[1];   // v2 송전탑

        // 해당 전선을 양방향 연결

        tree[v1].add(v2);   // v1 송전탑에 v2 송전탑을 연결

        tree[v2].add(v1);   // v2 송전탑에 v1 송전탑을 연결

    }

 

 

1. [v1, v2] 전선을 하나씩 끊는다.

2. v1 송전탑이 속하는 전력망의 송전탑 개수를 BFS로 탐색해서 구한다.

3. v2 송전탑이 속하는 전력망의 송전탑 개수를 BFS로 탐색해서 구한다.

4. 2번과 3번에서 구한 수의 차이를 구하고, 최솟값을 갱신한다.

5. 모든 전선을 한 번씩 끊을 때까지 1 ~ 4번을 반복한다.

 

참고로 각 송전탑의 리스트에서 송전탑을 제거하는 메서드(remove)를 사용할 때에는 Integer로 형변환을 반드시 해야한다.

List의 remove 메서드는 다음과 같이 remove(int index), remove(Object o)로 다중정의 되어있다.

우리는 remove(Object o)가 선택되기를 원하지만, 만약 여기서 그냥 int v1또는 int v2를 매개변수로 넘겨주면 자바 컴파일러는 remove(int index)로 인식을 하기 때문에 예상대로 동작하지 않게 된다.

그래서 Integer로 형 변환을 해서 remove(Object o)로 선택되도록 강제하는 것이다.

 

    // 모든 전선 탐색

    for (int[] wire : wires) {

        int v1 = wire[0];   // v1 송전탑

        int v2 = wire[1];   // v2 송전탑

       

        // 해당 전선을 양방향 제거

        // Integer로 형변환하지 않으면 remove 메서드는 매개변수를 Object o가 아닌 int index로 인식해서 오류 발생

        tree[v1].remove((Integer)v2);   // v1 송전탑에 연결된 v2 송전탑 끊기

        tree[v2].remove((Integer)v1);   // v2 송전탑에 연결된 v1 송전탑 끊기

       

        // bfs(v1, n) = v1 송전탑이 속한 전력망의 송전탑 개수

        // bfs(v2, n) = v2 송전탑이 속한 전력망의 송전탑 개수

        // 두 전력망이 가지고 있는 송전탑 개수의 차이(절대값)

        int diff = Math.abs(bfs(v1, n) - bfs(v2, n));

       

        // 해당 전선을 다시 양방향 연결

        tree[v1].add(v2);   // v1 송전탑에 v2 송전탑을 연결

        tree[v2].add(v1);   // v2 송전탑에 v1 송전탑을 연결

       

        // 두 전력망이 가지고 있는 송전탑 개수의 차이(절대값)의 최솟값 갱신

        answer = Math.min(answer, diff);

    }

   

    return answer;  // 두 전력망이 가지고 있는 송전탑 개수의 차이(절대값)의 최솟값 리턴

 

 

전선을 끊은 뒤의 각 송전탑이 속한 전력망의 송전탑 개수를 구할 bfs 메서드는 다음과 같다.

큐와 방문 체크 배열을 사용하는 전형적인 BFS 코드와 일치한다.

방문하지 않은 새로운 송전탑을 발견할 때마다 count를 1씩 증가시키고, 최종 count를 리턴한다.

 

    // start(시작) 송전탑이 속한 전력망 탐색

    public int bfs(int start, int n) {

        Queue<Integer> queue = new LinkedList<>();  // 송전탑을 넣을 큐

        boolean[] visited = new boolean[n + 1];     // 송전탑 방문 체크 배열

        int count = 0;  // start(시작) 송전탑이 속한 전력망의 송전탑 개수

       

        queue.add(start);       // 큐에 시작 전력망 추가

        visited[start] = true;  // 시작 전력망을 방문 체크

        count++;    // 시작 송전탑이 속한 전력망의 송전탑 개수 1 증가

       

        // 큐가 빌 때까지 (시작 전력망이 속한 송전탑을 모두 탐색할 때까지) 반복

        while (!queue.isEmpty()) {

            int now = queue.poll();     // 현재 전력망을 큐에서 뽑기

           

            // 현재 전력망과 연결된 송전탑들을 모두 탐색

            for (int next : tree[now]) {

                if (!visited[next]) {   // 연결된 송전탑을 방문하지 않았다면

                    queue.add(next);    // 연결된 송전탑을 큐에 추가

                    visited[next] = true;   // 연결된 송전탑을 방문 체크

                    count++;    // 시작 송전탑이 속한 전력망의 송전탑 개수 1 증가

                }

            }

        }

       

        return count;   // start(시작) 송전탑이 속한 전력망의 송전탑 개수 리턴

    }

 

---

전체 코드

import java.util.*;
 
class Solution {
    List<Integer>[] tree;   // 트리 리스트 배열
    
    public int solution(int n, int[][] wires) {
        int answer = Integer.MAX_VALUE; // 두 전력망이 가지고 있는 송전탑 개수의 차이(절대값)의 최솟값
        tree = new ArrayList[n + 1];    // 트리 리스트의 배열이 인덱스를 n까지 가질 수 있도록 초기화
        
        // 각 송전탑(1부터 n까지)이 모두 ArrayList를 가질 수 있도록 초기화
        for (int i = 1; i <= n; i++) {
            tree[i] = new ArrayList<>();
        }
        
        // 모든 전선 연결
        for (int[] wire : wires) {
            int v1 = wire[0];   // v1 송전탑
            int v2 = wire[1];   // v2 송전탑
            // 해당 전선을 양방향 연결
            tree[v1].add(v2);   // v1 송전탑에 v2 송전탑을 연결
            tree[v2].add(v1);   // v2 송전탑에 v1 송전탑을 연결
        }
        
        // 모든 전선 탐색
        for (int[] wire : wires) {
            int v1 = wire[0];   // v1 송전탑
            int v2 = wire[1];   // v2 송전탑
            
            // 해당 전선을 양방향 제거
            // Integer로 형변환하지 않으면 remove 메서드는 매개변수를 Object o가 아닌 int index로 인식해서 오류 발생
            tree[v1].remove((Integer)v2);   // v1 송전탑에 연결된 v2 송전탑 끊기
            tree[v2].remove((Integer)v1);   // v2 송전탑에 연결된 v1 송전탑 끊기
            
            // bfs(v1, n) = v1 송전탑이 속한 전력망의 송전탑 개수
            // bfs(v2, n) = v2 송전탑이 속한 전력망의 송전탑 개수
            // 두 전력망이 가지고 있는 송전탑 개수의 차이(절대값)
            int diff = Math.abs(bfs(v1, n) - bfs(v2, n));
            
            // 해당 전선을 다시 양방향 연결
            tree[v1].add(v2);   // v1 송전탑에 v2 송전탑을 연결
            tree[v2].add(v1);   // v2 송전탑에 v1 송전탑을 연결
            
            // 두 전력망이 가지고 있는 송전탑 개수의 차이(절대값)의 최솟값 갱신
            answer = Math.min(answer, diff);
        }
        
        return answer;  // 두 전력망이 가지고 있는 송전탑 개수의 차이(절대값)의 최솟값 리턴
    }
    
    // start(시작) 송전탑이 속한 전력망 탐색
    public int bfs(int start, int n) {
        Queue<Integer> queue = new LinkedList<>();  // 송전탑을 넣을 큐
        boolean[] visited = new boolean[n + 1];     // 송전탑 방문 체크 배열
        int count = 0;  // start(시작) 송전탑이 속한 전력망의 송전탑 개수
        
        queue.add(start);       // 큐에 시작 전력망 추가
        visited[start] = true;  // 시작 전력망을 방문 체크
        count++;    // 시작 송전탑이 속한 전력망의 송전탑 개수 1 증가
        
        // 큐가 빌 때까지 (시작 전력망이 속한 송전탑을 모두 탐색할 때까지) 반복
        while (!queue.isEmpty()) {
            int now = queue.poll();     // 현재 전력망을 큐에서 뽑기
            
            // 현재 전력망과 연결된 송전탑들을 모두 탐색
            for (int next : tree[now]) {
                if (!visited[next]) {   // 연결된 송전탑을 방문하지 않았다면
                    queue.add(next);    // 연결된 송전탑을 큐에 추가
                    visited[next] = true;   // 연결된 송전탑을 방문 체크
                    count++;    // 시작 송전탑이 속한 전력망의 송전탑 개수 1 증가
                }
            }
        }
        
        return count;   // start(시작) 송전탑이 속한 전력망의 송전탑 개수 리턴
    }
}