[프로그래머스] 전력망을 둘로 나누기 (위클리 챌린지 9주차) Javascript

문제 내용

하나의 트리 형태로 값이 주어진다.

이 중에서 하나의 연결된 edge 를 자르면 2개의 트리가 구성이 된다.

나눠진 2개의 트리의 각각 node 의 수가 있는데 그 수 끼리의 차를 구해라.

 

 

제한사항

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

---

전체 코드

function solution(n, wires) {
    // 1. 답을 저장할 answer 를 생성함 (정답은 최소값을 구하는 것이므로 초기 값을 Infinity 로 주었음.)
    let answer = Infinity;
    // 2. 주어진 wires 를 저장할 배열 nodes 를 생성하였음 (2차원 배열로 사용할 예정.)
    let nodes = [];

    // 3. wires 의 값들을 nodes 에 저장하기 위한 반복문
    for (let wire of wires) {
        // 4. nodes 에 wire 값을 추가
        if (nodes[wire[0]] == null) {
            nodes[wire[0]] = [wire[1]];
        } else {
            nodes[wire[0]].push(wire[1]);
        }
        // 5. 그래프가 방향이 없는 그래프이므로 양쪽으로 추가했음
        if (nodes[wire[1]] == null) {
            nodes[wire[1]] = [wire[0]];
        } else {
            nodes[wire[1]].push(wire[0]);
        }
    }

    // 6. node 를 방문했는지 안했는지 파악하기 위한 visted 배열 (초기값은 모두 false 로 하고, wires 의 값들이 0 부터 시작하는 것이 아닌 1부터 시작해서 n + 1 만큼 생성하였음)
    let visited = Array(n + 1).fill(false);
    // 7. 몇 개의 node 를 방문했는지 저장하기 위한 count 생성
    let count = 0;

    // 8. 모든 node 를 방문하기 위한 반복문
    for (let i = 1; i <= n; i++) {
        // 9. 방문한 node 에서 다른 곳으로 갈 수 있으면 그 곳을 방문하기 위한 반복문
        for (let j = 0; j < nodes[i].length; j++) {
            // 10. visted 와 count 의 값을 초기화함 (이전에 사용했을 수도 있기 때문)
            visited = Array(n + 1).fill(false);
            count = 0;
            // 11. 현재 node 값은 방문하지 말아야 하므로 true 로 설정하 
            visited[i] = true;
            // 12. find 함수 호출
            find(nodes[i][j]);
            // 13. 새로 설정된 count 를 통해 답을 최신화함
            answer = Math.min(Math.abs(count * 2 - n), answer);
        }
    }

    // 14. 방문할 값 (next) 을 파라미터로 받음
    function find(next) {
        // 15. 만약 방문할 값이 방문하지 않았다면
        if (!visited[next]) {
            // count 를 1 증가시키고
            count += 1;
            // 방문했다고 체크함
            visited[next] = true;
        
        // 16. 만약 방문했다면
        } else {
            // 더 찾을 필요 없으므로 종료
            return;
        }

        // 17. 방문한 값에서 다른 곳으로 방문할 수 있는 지 확인하는 반복문
        for (let k = 0; k < nodes[next].length; k++) {
            // 18. 만약 다음 값으로 방문할 수 있다면 (다음 값을 아직 방문하지 않았다면)
            if (!visited[nodes[next][k]]) {
                // 방문함
                find(nodes[next][k]);
            }
        }
    }

    return answer;
}

 

 

문제의 첫번째 예시를 보면

n	wires	return
9	[[1, 3], [2, 3], [3, 4], [4, 5], [4, 6], [4, 7], [7, 8], [7, 9]]	3

 

이렇게 주어졌다.

이렇게 트리가 형성이 된다.

 

5번 까지 진행 (wires 를 nodes 에 추가) 을 하고 nodes 를 보면

[
  <1 empty item>, 
  [ 3 ],
  [ 3 ],  
  [ 1, 2, 4 ], 
  [ 3, 5, 6, 7 ], 
  [ 4 ], 
  [ 4 ],
  [ 4, 8, 9 ],
  [ 7 ],
  [ 7 ] 
]

이런 식으로 저장이 되었다.

0번 index 에는 값이 저장되지 않았고

나머지는 정상적으로 저장이 되었다.

 

6, 7 번에서 visted 배열과 count 를 생성해주고

// 8. 모든 node 를 방문하기 위한 반복문
    for (let i = 1; i <= n; i++) {
        // 9. 방문한 node 에서 다른 곳으로 갈 수 있으면 그 곳을 방문하기 위한 반복문
        for (let j = 0; j < nodes[i].length; j++) {
            // 10. visted 와 count 의 값을 초기화함 (이전에 사용했을 수도 있기 때문)
            visited = Array(n + 1).fill(false);
            count = 0;
            // 11. 현재 node 값은 방문하지 말아야 하므로 true 로 설정하 
            visited[i] = true;
            // 12. find 함수 호출
            find(nodes[i][j]);
            // 13. 새로 설정된 count 를 통해 답을 최신화함
            answer = Math.min(Math.abs(count * 2 - n), answer);
        }
    }

8번을 진행하면

i = 1, j = 0 이다.

visited[i] (visited[1]) = true 로 설정하고

nodes[i][j] (nodes[1][0] = 3) 에 대해 find 함수를 호출한다.

 

// 14. 방문할 값 (next) 을 파라미터로 받음
    function find(next) {
        // 15. 만약 방문할 값이 방문하지 않았다면
        if (!visited[next]) {
            // count 를 1 증가시키고
            count += 1;
            // 방문했다고 체크함
            visited[next] = true;
        
        // 16. 만약 방문했다면
        } else {
            // 더 찾을 필요 없으므로 종료
            return;
        }

        // 17. 방문한 값에서 다른 곳으로 방문할 수 있는 지 확인하는 반복문
        for (let k = 0; k < nodes[next].length; k++) {
            // 18. 만약 다음 값으로 방문할 수 있다면 (다음 값을 아직 방문하지 않았다면)
            if (!visited[nodes[next][k]]) {
                // 방문함
                find(nodes[next][k]);
            }
        }
    }

현재 find 함수에 next 의 값은 node[1][0] = 3 이다.

visited[3] 은 아직 false 이므로 15 번 조건문에 해당한다.

따라서 count += 1 이 되어 현재 count = 1 이 된다.

그리고 visited[3] = true, 현재 visited[1] 과 visited[3] 이 true 가 되었고 그 외에는 모두 false 이다.

17 번 반복문이 실행 되고

nodes[next] 는 nodes[3] 이고 이 배열에는 [ 1, 2, 4 ] 가 들어있다.

여기서 visited[1] 은 true 이므로 18 번 조건문에 해당하지 않아 find 가 실행되지 않는다.

visited[2] 와 visited[4] 는 false 이므로 18 번 조건에 해당하여 find(2) 와 find(4) 가 실행 된다.

 

 

find(2) 가 진행이 되면 2 에서는 더이상 방문할 곳이 없으므로 find 는 종료가 된다.

 

그리고 find(4) 가 진행이 된다.

 

이런 방식으로 모두 진행이 되고

    for (let i = 1; i <= n; i++) {
        for (let j = 0; j < nodes[i].length; j++) {
            // 중략
            // 13. 새로 설정된 count 를 통해 답을 최신화함
            answer = Math.min(Math.abs(count * 2 - n), answer);
        }
    }

count = 8 이 되고

abs(count * 2 - n) = abs(8 * 2 - 9) = 7 이 된다.

 

이런 방식으로 진행하면 

i = 3 이고 nodes[3][j] = 4 일 때,

count = 6 이 되고 

abs(count * 2 - n) = abs(6 * 2 - 9) = 3 이 되어 최솟값이 된다.

 

---

결론

n 의 크기가 100 이하인 자연수이므로 완전탐색을 해도 상관 없을 것 같아서 그렇게 진행함.

 

 

출처 : 프로그래머스 위클리 챌린지 9주차 전력망을 둘로 나누기
https://programmers.co.kr/learn/courses/30/lessons/86971

코딩테스트 연습 - 9주차