문제 출처 - 프로그래머스
문제(정확한 문제는 위 링크 참조)
n개의 노드가 있는 그래프가 있다. 각 노드는 1부터 n까지의 번호가 적혀있다. 최단 경로를 전제했을 때 1번 노드로부터 가장 멀리 떨어진 노드의 개수를 리턴하라.입출력 예시 - 자바스크립트 버전
노드의 개수 n과 간선에 대한 정보가 담긴 2차원 배열 vertex가 매개변수로 주어진다. (ex) n = 6 vertex = [[3,6],[4,3],[3,2],[1,3],[1,2],[2,4],[5,2]] return 3 (설명) 1번 노드로부터 가장 멀리 떨어진 노드는 4,5,6 이므로 3을 리턴
시간 초과 실패한 코드 1
- BFS, queue를 이용
function solution(n, edge){ // 큐의 가장 첫번째 원소를 head로 설정 var head = 1; // 큐를 구현할 배열을 만듦 var q = [head]; // 노드 방문 여부를 boolean값으로 저장할 배열 생성 var b = new Array(n+1); b[head] = true; // 1번 노드와의 거리를 저장할 배열 생성 var d = new Array(n+1); d[0] = null; // 시작할 헤드(노드 1)의 거리는 0 d[head] = 0; // q에 원소가 있는 동안 bfs 탐색하며, 1번 노드와의 거리를 d배열에 저장. while(q.length !== 0) { for(var i = 1 ; i <= n ; i++) { if(edge.some(v => v.includes(i) && v.includes(head)) && b[i] !== true) { q.push(i); b[i] = true; d[i] = d[head]+1; } } q.shift(); head = q[0]; } // d배열에서 가장 큰 값을 찾은 뒤, 그 값을 갖고 있는 원소의 개수를 세어 리턴 var max = Math.max(...d); return d.filter(i=> i === max).length; }
시간 초과로 실패한 코드 2 (1답안 보다 테스트 케이스 더 많이 통과했으나 2개 실패)
- edge를 매번 전부 탐색하는 부분을 개선. splice를 사용해서 탐색할 때마다 edge 크기를 줄여나감.
- 그리고 1답안에서는 큐의 원소가 전부 사라질 때까지 탐색했는데 그러면 정작 edge는 텅비었는데 쓸데없이 탐색 하는 횟수가 늘어나서 edge의 원소가 전부 사라질 때까지 while문 돌림
function solution(n, edge){ var head = 1; var q = [head]; // 방문 여부 var b = new Array(n+1); b[head] = true; // 현 헤드와의 거리 저장 var d = new Array(n+1); d[0] = null; d[head] = 0; let j; while(edge.length !== 0) { j = 0; while(j < edge.length) { if(edge[j].includes(head)) { edge[j] = edge[j].filter(k => k !== head); if(!b[edge[j][0]]) { q.push(edge[j][0]); b[edge[j][0]] = true; d[edge[j][0]] = d[head]+1; } edge.splice(j, 1); j--; } j++; } q.shift(); head = q[0]; } var max = Math.max(...d); return d.filter(i => i === max).length; }
테스트 케이스 모조리 다 틀린 코드
- 왜 몇 개가 통과못하는 것도 아니고 다 틀리지...? 어디가 틀렸는지 잘 모르겠는 코드ㅠㅠ empty 때문인가
- 탐색하기 쉽도록 구조를 바꾼 다음에 bfs 돌림
- 그러나 제출 누르자마자 테스트 케이스 다 틀림..
function solution(n, edge){ var head = 1; var q = [head]; // 방문 여부 var b = new Array(n+1); b[head] = true; // 현 헤드와의 거리 저장 var d = new Array(n+1); d[0] = null; d[head] = 0; var arr = []; for(var j = 0 ; j < n ; j++) { arr.push([]); } for(var i of edge) { if(i[0] < i[1]) { arr[i[0]-1][i[1]-1] = 1; } else { arr[i[1]-1][i[0]-1] = 1; } } while(q.length !== 0) { for(var k = head ; k < arr[head-1].length ; k++) { if(arr[head-1][k] === 1 && b[k+1] !== true) { q.push(k+1); b[k+1] = true; d[k+1] = d[head] + 1; } } q.shift(); head = q[0]; } var max = Math.max(...d); return d.filter(i => i === max).length; }
다른 분 정답 보고 다시 짠 코드(통과)
function solution(n, edge) { // 2차원 배열 만들기 const arr = Array(n+1).fill(null).map(()=>Array()); const queue = [[1,0]]; const dist = [null]; for(let i of edge) { arr[i[0]].push(i[1]); arr[i[1]].push(i[0]); } inputQueue(1,1); while(queue.length > 0) { const shifted = queue.shift(); // 이 조건은 노드 1이 방문한 노드로서 지워지지 않았기 때문 if(dist == null) dist[shifted[0]] = shifted[1]; inputQueue(shifted[0], dist[shifted[0]] + 1); } // 거리 최대값의 개수 리턴 const max = Math.max(...dist); return dist.filter(i=> i === max).length; function inputQueue(i, weight) { const len = arr[i].length; // 큐에 푸시 for(let j=0 ; j < len ; j++) { const num = arr[i].shift(); queue.push([num, weight]); // 방문한 노드 지우기 for(let k =1 ; k <=n ; k++) { const index = arr[k].indexOf(num); if(index != -1) { arr[k].splice(index,1); } } } } }