프로그래머스
SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프
programmers.co.kr
[문제 요구 사항]
- n개의 노드와 n-1개의 간선으로 이루어진 트리가 주어졌다. 이 때, 한 개의 간선을 끊었을 때 두 트리의 노드 차이를 최소한으로 하고 그 값을 구하여라
[문제 아이디어]
1. 모든 간선을 순회하며 하나씩 끊는다. 그리고 한 트리를 bfs를 돌리면 작은 트리의 노드 개수가 나온다. 이 때, bfs 개수 - (n-bfs 개수)가 최소가 되는 값을 찾는다.
- 시간 복잡도 예상 : 간선의 개수 * bfs worst case = (n-1) * (n-1) = n^2
- 공간 복잡도 예상 : (방문체크 배열 길이 + queue의 최대 깊이) * 간선 개수(=반복 횟수) = 2n * (n-1) = n^2
2. 트리를 그리고 쌓아서 올라간다. 이를 DP로 표현하고 bfs 개수 - (n-bfs 개수)를 구해서 마지막에 가장 작은 값을 반환한다.
- 시간 복잡도 예상 : 일차 순회 = n
- 공간 복잡도 예상 : 순회 * 필요한 변수 개수(3-4) = 3n = n
2번으로 하고 싶은데, 규칙을 못 잡았다ㅣ. 리프노드를 1로 잡고 올렸는데 중간에 충돌하는 경우 규칙이 충돌해서 값이 이상해질 것으로 보였음. 그래서 1차 구현은 1번 아이디어로 진행
[1번 풀이 = 내 풀이]
function solution(n, wires) {
let answer = 99999999
const disconnectWire = (disconnectedWireNumber) => {
return wires.filter((wire,i) => i !== disconnectedWireNumber)
}
const bfs = (changeWires) => {
const visited = Array.from({length : n+1}, () => false)
visited[1] = true
const queue = [1]
let cnt = 0
while (queue.length > 0) {
cnt += 1
const node = queue.pop()
for (let i =0; i< changeWires.length; i +=1) {
if(changeWires[i][0] === node && visited[changeWires[i][1]] === false) {
visited[changeWires[i][1]]= true
queue.push(changeWires[i][1])
}
if(changeWires[i][1] === node && visited[changeWires[i][0]] === false) {
visited[changeWires[i][0]] = true
queue.push(changeWires[i][0])
}
}
}
return Math.abs(n- cnt *2)
}
for (let i =0; i<n; i+=1) {
const value = bfs(disconnectWire(i))
if (value < answer) {
answer = value
}
}
return answer;
}
- 간선을 순회하며 끊어진 간선 배열을 만들고 이를 전달하여서 bfs를 돌림.
[2번 풀이 = 프로그래머스 딴 분 풀이]
function solution(n, wires) {
let ans = 99999999
// graph 생성
const graph = Array.from({length : n}, () => [])
for (const edge of wires) {
graph[edge[0]-1].push(edge[1]-1)
graph[edge[1]-1].push(edge[0]-1)
}
// Tree 형태로 변환
const parents = new Array(n).fill(-1)
const queue = [0]
for (let i=0; i<queue.length; i++){
const u = queue[i]
for (const v of graph[u]) if (v != parents[u]) {
parents[v] = u
queue.push(v)
}
}
// Tree 기반 간선 계산
const dp = new Array(n).fill(1)
for (let i = queue.length; i>0; i--){
const v = queue[i]
dp[parents[v]] += dp[v]
const minValue = Math.abs(n-2*dp[v]);
if (ans > minValue) ans = minValue
}
console.log(graph, parents, ans)
return ans;
}
- 다른 분의 풀이인데, 약어를 많이 쓰셔서 변수명만 이해하기 쉽게 바꾸었다.
- 아이디어는 동일한데 나는 graph로 생각해서 dp를 제대로 적용하지 못했다. 하지만, 이 분은 이를 부모-자식 관계로 정리하여서 순서를 만들었고 이를 통해서 dp를 생성할 수 있었다. 마지막 자식부터 부모로부터 dp를 생성하니 내 생각과 동일하게 할 수 있었다.
[고쳐야할 점]
- 오랜만에 풀어서 좀 많이 느렸다. 6배 정도 빨라져야한다.
- 코테 떨어진 적이 많은데 1번과 2번 차이 아닐까 싶다. 푸는 게 중요한 게 아니라 잘 푸는 것이 중요하다.
'TIL > 신규 풀이' 카테고리의 다른 글
[프로그래머스_완전탐색] 소수찾기 (0) | 2024.11.10 |
---|