코드만 궁금한 분은 깃허브링크
GitHub - Rhyankwon/algorithms
Contribute to Rhyankwon/algorithms development by creating an account on GitHub.
github.com
문제 설명 ㄱㄱ
문제는 읽어보시고, 어.. 간단히 설명하면,
1. 트리가 하나 주어지는데 거기에서 어느 간선 하나를 자른다.
2. 이 때 주어진 트리는 두개의 다른 트리로 나뉘어지는데
3. 두 트리의 노드의 갯수 차이가 최소인 경우를 찾아서 그 차이값을 리턴하면 된다.
다음은 내가 풀이한.. 문제 해결 논리이다. 간단히 얘기하자면 양쪽 노드의 갯수 균형이 적당히 맞는 트리를 만들면서 그 때의 최상단 노드를 찾고 그 노드의 자식노드 중 하나를 잘라내면 된다.
1. 주어진 wires 변수로 그래프를 만들고, 각 노드 번호별로 '연결된 노드 갯수'를 저장할 리스트를 선언한다.
2. 자식 노드가 한개인 노드(트리의 최하단 노드)들을 모두 조사한다.
3. 위에서 찾아낸 노드들을 삭제하면서 해당 노드와 간선으로 연결돼있던 노드에 각각 '연결된 노드 갯수'를 1씩 더한다.
4. 다시 자식 노드가 한개인 노드들을 모두 조사하는데,
5. 이 때에는 3번에서 계산했던 연결된 노드 갯수를 비교해서 그 중, 연결됏던 노드 수가 가장 적은 노드만 삭제한다.
6. 이 때 이 노드의 '연결된 노드 갯수'에 1을 더하고 이 노드의 상위 노드에 현재 노드의 '연결된 노드 갯수'를 더한다.
7. 4~6을 반복하다가 트리 최상단까지 오면(그래프 길이가 1이 되면) 반복문을 종료하고
8. '연결된 노드 갯수' 리스트에서 두번째로 큰 값 X(첫번째로 큰 값은 최상단 노드의 연결노드 값이라 전체 노드의 수 - 1이 저장돼있음.)를 찾아서 절대값(전체 노드의 수 - (전체 노드의 수 - X))을 리턴한다.
최대한 쉽게 설명하려고 했는데 이해가 될지 모르겠다. 그래프의 끝단부터 탐색하는데 이 때 각 노드마다 전체 자손노드의 갯수가 작은 순서로 탐색하면서 최상단 노드를 찾았을 때 각 자식노드들에 분포된 노드들의 갯수가 최대한 비슷하도록 하는게 문제의 핵심이다.
문제없이 잘 풀린다.
------------------잡담--------------------
풀고 나서 다른 사람들의 풀이를 봤는데 막 몇줄만에 푼 사람도 있고 또 내가 처음 보는 함수를 이용해서 푼 사람들도 있다. 아직 그 사람들 코드를 검토해본건 아니지만 몇줄로 해결한 사람은 정말 어떻게 그렇게 풀 아이디어를 낸건지 정말 경이롭다. 물론 나도 내가 생각했을 때에 최선의 코드로 짠거라 내 코드가 별로라고 생각하는건 아니지만.. 확실히 다른 사람들의 코드를 검토해보고 싶다. dfs로 푼 사람들도 많던데 어떻게 dfs로 풀 생각을 했는지 신기하다 ㅋㅋ
'코딩테스트 > 프로그래머스' 카테고리의 다른 글
| 프로그래머스 10주차 교점에 별 만들기 풀이/코드 (파이썬) (0) | 2021.10.28 |
|---|---|
| 프로그래머스 단어 변환 문제 해설/코드 (파이썬), BFS활용문제 (0) | 2021.10.12 |
| 프로그래머스 8주차 위클리 챌린지 최소직사각형 문제 해설/코드 (파이썬) (0) | 2021.09.30 |
| 프로그래머스 124 나라의 숫자.. 푸는데.. 앞으로는 수학 쪽 문제를 더 많이 풀어야할 것 같다. (0) | 2021.09.21 |
| 프로그래머스 월간 챌린지 금과 은 운반하기 해설/코드 (파이썬) (2) | 2021.09.21 |