[프로그래머스][Java][Lv. 2] 전력망을 둘로 나누기

문제 설명

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

 

---

 

제한 사항

 

---

 

입출력 예

---

풀이

import java.util.HashMap;
import java.util.ArrayList;

class Solution {
    HashMap<Integer, ArrayList<Integer>> numMap = new HashMap<>();
    ArrayList<Integer> foundList = new ArrayList<>();
    
    public int solution(int n, int[][] wires) {
        int answer = Integer.MAX_VALUE;
        
        for (int i = 0; i < wires.length; i++) {
            for (int j = 0; j < 2; j++) {
                if (!numMap.containsKey(wires[i][j])) {
                    ArrayList<Integer> linkedNodeList = new ArrayList<>();
                    linkedNodeList.add(wires[i][1 - j]);
                    numMap.put(wires[i][j], linkedNodeList);
                } else {
                    numMap.get(wires[i][j]).add(wires[i][1 - j]);
                }
            }
        }
        
        for (int i = 0; i < wires.length; i++) {
            foundList.clear();
            getCount(numMap.get(wires[i][0]), wires[i][1]);
            int result = foundList.size() == 0 ? 1 : foundList.size();
            answer = Math.min(answer, Math.abs(2 * result - n));
        }
        return answer;
    }
    
    public void getCount(ArrayList<Integer> linkedNodeList, Integer second) {
        for (Integer num : linkedNodeList) {
            if (num == second) continue;
            
            if (!foundList.contains(num)) {
                foundList.add(num);
                getCount(numMap.get(num), second);
            }
        }
    }
}

---

후기

보통 이런 문제가 나오면 노드 클래스를 만들어서 서로 연결시키고 탐색하는 과정을 거치는데 이번에는 굳이 클래스를 만들지 않고 Map을 사용했다. 사실 문제에서 원하는건 연결을 끊어버렸을 때 나뉘는 두 그룹의 크기를 구하는거여서 처음에는 Set만으로 개수만 구하려고 했는데 이렇게하면 그룹을 두 개만 만들어 구성하는데 문제가 있었다. [a, b]에서 연결되는 숫자를 가지고 각 그룹에 포함시켜야 하는데 연결되는 부분이 연속되지 않고 저 뒤에 있으면 제대로 그룹에 속하지 않는 문제가 있었다. 그래서 그냥 결국 원래 방식대로 하기로 했다.