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

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

728x90

프로그래머스에서 9주째 하고 있는 위클리 챌린지입니다. 가장 좋아요를 많이 받으면 상품을 준다고 하네요. 저는 그정도 수준은 아닌지라 프로그래머스로 코테 준비도 할 겸 풀어볼 문제가 늘어난다는 것에 만족하면서 문제를 풀고 있습니다.

솔직히 처음에 문제를 보고 제가 레벨 2로 지정된 문제조차 못푸는 건가 하면서 한탄을 금치 못했었는데요. 확실히 저는 그래프(or 트리) 문제에 많이 취약하다는 것을 깨닫게 되었습니다. (그리고 생각보다 더 문제를 어렵게 바라본다는 점두요.)

문제 시작하겠습니다!

전력망을 둘로 나누기

문제 설명

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

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

제한사항

n은 2 이상 100 이하인 자연수입니다.

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

n-1인 정수형 2차원 배열입니다.

입출력 예

nwiresresult

9 [[1,3],[2,3],[3,4],[4,5],[4,6],[4,7],[7,8],[7,9]] 3 4 [[1,2],[2,3],[3,4]] 0 7 [[1,2],[2,7],[3,7],[3,4],[4,5],[6,7]] 1

입출력 예 설명

입출력 예 #1

다음 그림은 주어진 입력을 해결하는 방법 중 하나를 나타낸 것입니다.

4번과 7번을 연결하는 전선을 끊으면 두 전력망은 각 6개와 3개의 송전탑을 가지며, 이보다 더 비슷한 개수로 전력망을 나눌 수 없습니다.

또 다른 방법으로는 3번과 4번을 연결하는 전선을 끊어도 최선의 정답을 도출할 수 있습니다.

입출력 예 #2

다음 그림은 주어진 입력을 해결하는 방법을 나타낸 것입니다.

2번과 3번을 연결하는 전선을 끊으면 두 전력망이 모두 2개의 송전탑을 가지게 되며, 이 방법이 최선입니다.

728x90

입출력 예 #3

다음 그림은 주어진 입력을 해결하는 방법을 나타낸 것입니다.

3번과 7번을 연결하는 전선을 끊으면 두 전력망이 각각 4개와 3개의 송전탑을 가지게 되며, 이 방법이 최선입니다.

아래는 제 정답코드입니다. dfs니 bfs니 하는 알고리즘은 잘 모릅니다만(정확히는 배웠었고, 써봤지만 까먹었다고 봐야하겠네요), 만들고 보니 dfs에 가까운 형태로 나타나 있다는 것을 확인할 수 있습니다. 단 이번 문제는 트리 구성이기 때문에 사이클이 존재하지 않는 점을 이용해서 visit 이라는 방문 확인 변수를 생략할 수 있었습니다.

import java.util.*; class Solution { ArrayList[] list; public int solution(int n, int[][] wires) { int answer = Integer.MAX_VALUE; list = new ArrayList[n+1]; for(int i=0;i(); //초기화 for(int i=0;i targetList = list[target]; for(int i=0;i

list는 각 노드에 어떤 노드가 연결되어 있는지를 확인하고자 하는 변수입니다. 만약 1번 노드가 3번과 연결되어 있다면 list[1]이 가진 arrayList에는 3이라는 변수가 존재하고 있을 겁니다.

그리고 값은 getNodeCount에서 구하게 되는데 target은 시작할 노드, exceptNumber는 제외해야 할 노드로 처음 exceptNumber는 분리해야할 노드가 됩니다. 이후에는 target을 제외시킴으로서 다음 노드에서 다시 이전 노드로 돌아오는 일(예를 들어 1에서 시작해 3의 노드 갯수를 파악하려다가 다시 1로 돌아가는 문제)을 방지할 수 있게 됩니다. 이는 트리 구조로 인해 사이클이 없어 특정 노드로 들어온 순간부터 그 노드와 다시 연결된 다른 노드가 없으므로 그 노드를 제외하면 문제 없이 갯수를 구할 수 있습니다.

그렇게 wires의 0번째에서 1번째를 제외한 노드의 개수와 1번째에서 0번째를 제외한 노드의 개수를 하나씩 다 잘라서 구해보면 최종 결과값이 도출되게 됩니다.

두 트리의 노드 개수의 차가 가장 적은 것만 알면 되기 때문에 크게 어렵지 않은 문제인 것 같습니다. 어렵다고 생각한 거에 비해 코드 작성이 꽤나 쉬웠고 한번도 안틀리고 생각한대로 바로 정답을 맞춰버려서 조금 당황한 부분도 있긴 합니다만, 아마 다들 어렵지 않게 풀 수 있을 것 같습니다. 풀기 전과 풀고 난 후의 난이도 갭이 좀 크네요!

728x90

from http://no-dev-nk.tistory.com/52 by ccl(A) rewrite - 2021-10-06 14:00:59