Written by nodejs-style
on 2021-10-09

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

문제 이해하기

n개의 송전탑이 전선을 통해 하나의 트리 형태 로 연결되어 있다.

로 연결되어 있다. 전선들 중 하나를 끊어서 네트워크를 2개로 분할하려고 한다.

분할된 두 전력망이 갖게 되는 송전탑의 개수를 구해야 한다.

데이터 추상화

n개의 송전 탑이 전선을 통해 하나의 트리 형태 로 연결되어 있다고 알려주고있다.

로 연결되어 있다고 알려주고있다. 전선 정보가 2차원 배열로 [ 송전탑, 송전탑] 형식으로 전달된다.

예를 들어 [[1,2], [2,3], [3,4]]인 전선 정보가 들어온다면

다음과 같은 모양을 가질 것이다.

예를 들어 전선 정보가 들어온다면 다음과 같은 모양을 가질 것이다. 위 그림과 같은 그래프를 추상화해보자. 2차원 배열의 행을 송전탑 1, 열을 송전탑 2로 생각해보자.

그리고 연결되어 있다면 1이라는 값을 할당하자.

0 1 2 3 4 0 0 0 0 0 0 1 0 0 1 0 0 2 0 1 0 1 0 3 0 0 1 0 1 4 0 0 0 1 0 위와 같은 형태로 추상화가 가능하다.

let ary = Array.from( Array(n+1), ()=> Array(n+1).fill(0));

그리고 연결되어 있다면 1이라는 값을 할당하자. 위와 같은 형태로 추상화가 가능하다. 각 송신탑을 방문했는지 여부를 확인하기 위해서 visit []이 필요하다.

let visit = Array(n+1).fill(0);

알고리즘

입력 파라미터로 wires값이 전달된다. 각 노드들이 연결되어 있음을 구현하자. 앞서 데이터 추상화의 첫 번째 부분에 해당한다.

// graph mapping wires.forEach( ([v1,v2]) => { ary[v1][v2] = 1; ary[v2][v1] = 1; }); 이제 전선들 중 하나를 끊어서, 네트워크를 분할한 다음. 연결된 송전탑의 개수를 받자.

ans = wires.reduce( (m, [v1, v2]) => { // 초기화 cnt = 0; visit.fill(0); // 전선 끊기 ary[v1][v2] = 0; ary[v2][v1] = 0; // 연결된 송전탑 개수 찾기 dfs(1); // 끊어진 전선 재 연결 ary[v1][v2] = 1; ary[v2][v1] = 1; }, n) 전체 송전탑의 개수에서 연결된 송전탑의 개수를 빼면, 다르게 연결된 송전탑의 개수를 구할 수 있다. 이 중 가장 적은 값을 반환하면 된다.

return Math.min(Math.abs(n - cnt - cnt), m );

구현

정리 및 느낀 점

이번에 풀어본 문제는 그래프 탐색이다. 그래프를 탐색하는 다양한 방법 중 dfs 방법을 사용하여 구현하였다.

그래프가 연결되어있음을 추상화하는 것이 매우 중요하다. 연결된 각 노드들을 2차원 배열로 매핑해주는 것이 필요하다.

방문 여부를 체크할 수 있는 배열을 만들어서 방문 여부를 또한 체크해야 한다.

그래프 탐색 알고리즘도 정리해서 블로깅 하자.

출처

https://programmers.co.kr/learn/courses/30/lessons/86971?language=javascript

from http://workshop-code.tistory.com/61 by ccl(A) rewrite - 2021-10-09 23:00:56

Top