전력망을 둘로 나누기 (프로그래머스, Level 2)

문제 설명

n개의 송전탑이 전선을 통해 하나의 트리 형태로 연결되어 있습니다. 당신은 이 전선들 중 하나를 끊어서 현재의 전력망 네트워크를 2개로 분할하려고 합니다. 이때, 두 전력망이 갖게 되는 송전탑의 개수를 최대한 비슷하게 맞추고자 합니다.

송전탑의 개수 n, 그리고 전선 정보 wires가 매개변수로 주어집니다. 전선들 중 하나를 끊어서 송전탑 개수가 가능한 비슷하도록 두 전력망으로 나누었을 때, 두 전력망이 가지고 있는 송전탑 개수의 차이(절대값)를 return 하도록 solution 함수를 완성해주세요.

---

제한사항

• n은 2 이상 100 이하인 자연수입니다.
• wires는 길이가 n-1인 정수형 2차원 배열입니다.
  • wires의 각 원소는 [v1, v2] 2개의 자연수로 이루어져 있으며, 이는 전력망의 v1번 송전탑과 v2번 송전탑이 전선으로 연결되어 있다는 것을 의미합니다.
  • 1 ≤ v1 < v2 ≤ n 입니다.
  • 전력망 네트워크가 하나의 트리 형태가 아닌 경우는 입력으로 주어지지 않습니다.

 

이번 문제는 대충 보아도 데이터끼리 서로 연결된 모양의 문제임을 알 수 있습니다.

데이터가 서로 연결되었다는 의미는 "트리" 구조형태의 데이터를 의미하며,

트리는 1개로 구성되어 있고 이를 나눌 경우에는 반드시 2개로 쪼개어지는 것을 알 수 있습니다.

* 2개로 쪼개어지는 개념만 잘 인지한다면 쉽게 풀어낼 수 있습니다.

 

사실 트리형태의 구조를 만들기 위해서는 2차원배열을 활용하는데..

2차원 배열에서의 트리구조에 대한 탐색과 정렬, 삽입 및 삭제등의 행위가 아직 잘 그려지지 않아서 Java에서 제공하는 컬렉션의 힘을 빌려서 풀어 보았습니다.    * 좀더 노력해야겠네요..ㅠ

 

먼저 데이터에 대해서 어떠한 연결고리가 주어지는지 데이터를 그룹화 하여 보았습니다.

아래 사진은 프로그래머스에서 제공하는 문제에 대한 설명 입니다.

4번과 7번을 자르면..

 

위 사진을 보면 1번값은 3번을 가지고 있습니다.

3번값은 1,2,4번을 가지고 있으며, 4번 값은 3,5,6,7번 값을 가지고 있습니다.

문제에서 처음 주어진 데이터는 2중배열 이면서 크기가 2로 주어지므로 반복문을 통해 쉽게 그룹화할 수 있습니다.

private static void groupping(HashMap<Integer, List<Integer>> group, 
    int wire[], int target, int value) {
    List<Integer> set;
    if (group.get(wire[target]) == null) {  //키 값이 없다면
        set = new ArrayList<>();  //최초 배열을 만들어주고
        set.add(wire[value]);  //데이터를 넣고
        group.put(wire[target], set); //등록합니다
    } else {
        set = group.get(wire[target]);
        boolean isAdd = true;  //해당값이 이미 존재하는지 확인합니다.
        for(int num : set) {
            if(num == wire[value]) {
                isAdd = false;
                break;
            }
        }
        if(isAdd) {  //해당값이 없는 값이라면
            set.add(wire[value]);  //더해줍니다.
        }
    }
}

public static int solution(int n, int[][] wires) {

    int answer = n; // 최대 수치

    HashMap<Integer, List<Integer>> group = new HashMap<>();
    for (int wire[] : wires) {   //0번과 1번에 대해서 각각 돌려줍니다.
        groupping(group, wire, 0, 1); 
        groupping(group, wire, 1, 0);
    }

}

 

데이터가 2중배열이면서 크기가 2이므로 0번값과 1번값에 대해서 key, value 작업을 해 줍니다.

이렇게 그룹핑을 해 주고 나면 데어터가 이쁘게 묶여서 나오게 됩니다.

 

데이터를 잘 묶어주고나면 이제 고민해야 되는 것이 바로 "금지대상" 입니다.

금지대상 의미는 주어진 2중배열에서의 값 1개를 사용하지 않는 의미 입니다.

 

첫번째 문제를 예로 들면,

[[1,3],[2,3],[3,4],[4,5],[4,6],[4,7],[7,8],[7,9]] 값에서 0번째 값인 [1,3] 이 없는 경우에 서로의 연결상태를 구하고,

다음으로 [2,3]이 없는 경우에서의 서로의 연결상태를 구합니다.

이러한 방법으로 처음부터 마지막값까지 한개씩 포함시키지 않으면서 서로의 연결여부를 확인하도록 합니다.

public static int solution(int n, int[][] wires) {

    int answer = n; // 최대 수치

    HashMap<Integer, List<Integer>> group = new HashMap<>();
    for (int wire[] : wires) {   //0번과 1번에 대해서 각각 돌려줍니다.
        groupping(group, wire, 0, 1); 
        groupping(group, wire, 1, 0);
    }

    int cursor = 0;
    while (cursor < wires.length) {
        int noMember[] = wires[cursor];  //빼야되는 항목 값 입니다.
        for (Integer me : group.keySet()) { //그룹핑된 데이터에서
            HashMap<Integer, Boolean> newGroup = new HashMap<>();
            if(me != noMember[0] && me != noMember[1]) {  //빼야되는 키 값이 아니면,
                makeLine(noMember, group, me, newGroup); //탐색을 시작합니다.
            }
        }
        cursor++;
    }

}

 

빼야되는 키 값이 시작되는 경우를 제외하고 반복문을 수행하도록 코드를 작성 하였습니다.

이제 탐색 코드를 고민할 차레 입니다.

private static void makeLine(int noMember[], HashMap<Integer, List<Integer>> group, 
    int me, HashMap<Integer, Boolean> newGroup) {	
    
    List<Integer> list = group.get(me);  //연결 데이터 목록
    for(int target : list) {
        if(me == noMember[0] || me == noMember[1] ) {  //키 값이 금지대상이면서
            if(target == noMember[0] || target == noMember[1]) {  //가야하는 목적지도 금지대상이면
                newGroup.put(me, true);  //키 값은 추가합니다(끝부분 개념)
                continue;  //다음 데이터를 조사하게 합니다.
            }
        }
        if(newGroup.get(target) == null ) {  //해당 값이 금지대상 값이 아니면,
            newGroup.put(target, true);  //추가하여주고
            makeLine(noMember, group, target, newGroup);  //계속해서 다음 노드를 찾아가게 합니다
        }
    }
    
}

 

탐색을 하면서 저장하는 데이터는 HashMap을 사용하였습니다.

HashMap을 사용하면 키 자체를 중복없이 넣기에 편리하고 마찬가지로 가져오는데도 쉽기 때문 입니다.

여기서의 중요한 조건은 "키 값이 금지대상이면서" + "가야하는 목적지도 금지대상" 이라는 조건 입니다.

 

첫번째 예시를 예를 들어 생각하여 보면,

포함되지 않아야하는 데이터가 0번째라 가정하여 봅니다. * 0번째 : [1, 3]

반복문에 의해서 지금 조사해야되는 첫번째 데이터는 키 값 2 이며, 키값 2는 데이터 3만 가지고 있습니다.

이러한 경우에 2 값은 아래 루트를 따르게 됩니다.

private static void makeLine(int noMember[], HashMap<Integer, List<Integer>> group, 
    int me, HashMap<Integer, Boolean> newGroup) {	
    
    List<Integer> list = group.get(me);  //연결 데이터 목록
    for(int target : list) {
        if(me == noMember[0] || me == noMember[1] ) {  //2값은 noMember 대상이 아닙니다!!
            if(target == noMember[0] || target == noMember[1]) { 
                newGroup.put(me, true); 
                continue; 
            }
        }
        if(newGroup.get(target) == null ) {  //2값이 없으니
            newGroup.put(target, true);  //추가하고
            makeLine(noMember, group, target, newGroup);  //2가 가지고 있는 3이 재귀를통해 들어갑니다
        }
    }
    
}

 

이렇게 3값을 가지고 makeLine 메소드는 다시 동작하게 됩니다.

3은 1, 2, 4 값을 가지고 있습니다.

이러한 경우 3은 "키 값이 금지대상이면서" + "가야하는 목적지도 금지대상" 이라는 조건을 가지고 있는 데이터 이므로 continue 구간에 한번 진입하게 됩니다.

 

그리고 2값을 다시 호출하게 되지만 2값은 이미 넣은 값이므로 넘어가게 됩니다.

마지막 4 값은 금지대상도 아니므로 다시 makeLine 메소드를 호출하게 됩니다.

 

이러한 루틴으로 데이터를 반복하여 탐색하게 하면 "금지대상"을 제외한 서로의 연결고리가 잘 이루어진 1줄로된 결과데이터를 얻을 수 있습니다.

이제 남은 것은 이러한 방법을 통해서 가장 짧은 차이를 구하는 것 입니다.

public static int solution(int n, int[][] wires) {

    int answer = n; // 최대 수치

    HashMap<Integer, List<Integer>> group = new HashMap<>();
    for (int wire[] : wires) {   //0번과 1번에 대해서 각각 돌려줍니다.
        groupping(group, wire, 0, 1); 
        groupping(group, wire, 1, 0);
    }

    int cursor = 0;
    while (cursor < wires.length) {
        int noMember[] = wires[cursor];  //빼야되는 항목 값 입니다.
        for (Integer me : group.keySet()) { //그룹핑된 데이터에서
            HashMap<Integer, Boolean> newGroup = new HashMap<>();
            if(me != noMember[0] && me != noMember[1]) {  //빼야되는 키 값이 아니면,
                makeLine(noMember, group, me, newGroup); //탐색을 시작합니다.
                
                int sum = Math.abs(newGroup.size() - Math.abs(newGroup.size() - n));
                if(sum < answer) answer= sum;
                
            }
        }
        cursor++;
    }

}

 

sum 이라는 계산방법을 잘 살펴보아야 합니다.

데이터가 트리구조로 되어 있기 때문에 할 수 있는 방법 입니다.

 

9개의 연결된 트리가 4개를 자르게 되면 5개가 남습니다.

그러면 5개에서 4개를 뺀 값 또는 4개에서 5개를 뺀 값의 절대값은 서로의 차이를 의미 합니다.

위 말을 고려하여 sum에 사용된 수식을 살펴보면 쉽게 이해할 수 있습니다.

 

하지만 한번 더 고려해야되는 점은 for에서의 반복문이 여러번 돌 필요가 없다는 점 입니다.

public static int solution(int n, int[][] wires) {

    int answer = n; 

    HashMap<Integer, List<Integer>> group = new HashMap<>();
    for (int wire[] : wires) {  
        groupping(group, wire, 0, 1); 
        groupping(group, wire, 1, 0);
    }

    int cursor = 0;
    while (cursor < wires.length) {
        int noMember[] = wires[cursor];  
        for (Integer me : group.keySet()) { 
            HashMap<Integer, Boolean> newGroup = new HashMap<>();
            if(me != noMember[0] && me != noMember[1]) { 
                makeLine(noMember, group, me, newGroup); 
                
                int sum = Math.abs(newGroup.size() - Math.abs(newGroup.size() - n));
                if(sum < answer) answer= sum;
                continue; //여기입니다!!!!!!!!!!!!!!  //여기입니다!!!!!!!!!!!!!!
                
            }
        }
        cursor++;
    }

}

 

while 내부의 for 반복문은 시작점의 위치만다를 뿐 결국에는 서로 잘려진 크기의 절반씩이기 때문 입니다.

시작점이 어디더라도 나누어진 값의 차이를 계산하는 것 이기 때문 입니다.

위 코드를 바탕으로 이제 제출을 하여 봅니다..

통과...

 

위 내용에 사용된 소스코드는 아래 제 깃허브에서 받아서 볼 수 있습니다.

 

https://github.com/TaeSeungRyu/sample/tree/main/프로그래머스

GitHub - TaeSeungRyu/sample

 

사실 2차원 배열을 활용하여 문제를 접근하는 것이 대부분의 방식인데..

아직 탐색과 트리구조가 어색한지라 쉽게 접근하지 못하는게 많이 아쉬웠던 문제였습니다..ㅠ

실력이 부족하므로 좀더 노력해야 겠습니다!

 

이상으로 전력망을 둘로 나누기 (프로그래머스, Level 2)에 대해서 살펴보았습니다.

궁금한점 또는 틀린부분은 언제든 연락주세요!👻