코드로 이해하기
솔직히 웬만한 설명은 다 구글링해서 나와있는거 아니까...
프로그래머스 문제
function solution(N, road, K) {
var max = 99999999;
var min = 99999999;
var minpos = -1;
var dist = new Array(N).fill(max);
var found = new Array(N).fill(false);
var map = new Array(N);
for (var i = 0; i < N; i++) {
map[i] = new Array(N).fill(max);
}
var x,y,time;
for(var j=0;j<road.length;j++){
x = road[j][0]-1;
y = road[j][1]-1;
time = road[j][2];
map[x][y] = Math.min(map[x][y],time);
map[y][x] = Math.min(map[y][x],time);
}
dist[0] = 0;
for(var i=0;i<N;i++){
minpos = -1;
min = max;
for(var j=0;j<N;j++){
if(dist[j] < min && found[j] == false) //같은 가장 가까운 거리라면 먼저나온애를 먼저처리
{
minpos = j;
min = dist[j];
}
}
//
found[minpos] = true;
for(var w=0;w<N;w++){
if(found[w] == false){
dist[w] = Math.min(dist[w], map[minpos][w]+dist[minpos]);
}
}
}
return dist.filter(function(e){ return e <=K }).length;
}역할
var max = 99999999;
var min = 99999999;
var minpos => 시작점과 가장 거리가 가까우면서 지나치지않은 정점
var dist => 1차원 시작점으로부터의 거리 배열
var found => 1차원 정점을 지나쳤는지 확인하는 배열
var map => 2차원 정점간의 연결 거리를 확인 하는 배열
var dist = new Array(N).fill(max);
var found = new Array(N).fill(false);
var map = new Array(N);
for (var i = 0; i < N; i++) {
map[i] = new Array(N).fill(max);
}
dist는 전부 최대 값으로 그리고 found는 전부 아직 안지났으니 false로 map의 경우는 각 행마다의 배열을 무한으로 채우기
var x,y,time;
for(var j=0;j<road.length;j++){
x = road[j][0]-1;
y = road[j][1]-1;
time = road[j][2];
map[x][y] = Math.min(map[x][y],time);
map[y][x] = Math.min(map[y][x],time);
}각 배열마다의 대각선을 기준으로 같은 A,B정점이어도 거리가 여러개일수있으니 그중 가장짧은거로 선택하게
Math.min사용
dist[0] = 0;시작지점을 0으로해서 시작
minpos = -1;
min = max;
for(var j=0;j<N;j++){
if(dist[j] < min && found[j] == false) //같은 가장 가까운 거리라면 먼저나온애를 먼저처리
{
minpos = j;
min = dist[j];
}
}현재 존재하는 dist배열에서 가장 작은 값을 선택 (처음은 0번째위치 자기자신)하여 그 값을 minpos로 지정하고 그때의 거리를 min으로 지정시킨다.
found[minpos] = true;
for(var w=0;w<N;w++){
if(found[w] == false){
dist[w] = Math.min(dist[w], map[minpos][w]+dist[minpos]);
}
} 지정한 정점을 다시 확인하지않게 true로 설정하고
for문을 돌면서 새로운 지점이라면 기존에 있던 dist내용과 새로운 방향을 비교해봐서 가장 작은 값으로 최신화를 해준다.
정리
1. 정점들간의 거리를 포함한 2차원배열 map을 생성
2. 전부 최대값이 들어간 dist배열을 생성하되 시작인 0번째 위치는 0으로 설정
3. min보다 작고 새로운 정점을 찾는다. (처음시작은 자기자신 정점 , 가장 작은 min을 가진 정점찾기)
4. 확인 한 정점은 true로 만들고 찾은 정점이 새로운 정점이라면
기존에 얻었던 거리와 새로 만들어서 계산한 거리를 비교해본다.
5. 마지막 filter는 필요한 거리를 넘어서지않는 것들의 갯수만 본다. (다익스트라랑은 많이 연관되어있지는 않음)
예시 (프로그래머스 1번예시)
ex)
dist[w] = Math.min(dist[w], map[minpos][w]+dist[minpos]); 을 보면
처음 실행할때 dist는 [0,무한,무한,무한,무한]이고 map[0]의 내용들은 [무한,1,무한,2,무한이다.
처음실행시 minpos는 0
w가 0일때 : dist[w]=0, map[minpos][w]+dist[minpos] = 무한 + 0
w가 1일때 : dist[w]=무한, map[minpos][w]+dist[minpos] = 1 + 0
w가 2일때 : dist[w]=무한, map[minpos][w]+dist[minpos] = 무한 + 0
w가 3일때 : dist[w]=무한, map[minpos][w]+dist[minpos] = 2 + 0
w가 4일때 : dist[w]=무한, map[minpos][w]+dist[minpos] = 무한 + 0
즉, dist[w]는 각각 최소값인 [0,1,무한,2,무한] 형태로 처음 for문을 돈 결과이다.
(=> 기준정점을 기준으로 바로 연결된 값들에만 영향을 끼쳤다.)
출처
다시한번 정리 (예시를 통해)
3번째 출력결과에서 첫번째 for문으로 index 3번째로 min이 4가 되면 index 4번째는 min과 4는 값이 같기때문에 for문을 돌지않아(
if(dist[j] < min && found[j] == false)의 min보다 작지 않는 결과) minpos가 3이므로 3번째 index가 true로 설정된다.
전체 for문은 마을을 지정해서 찾는 횟수이고 그때 해당하는 마을선택 기준은 이전 연결을 통해 dist가 최솟값이 되는 minpos를 기준으로 해당
found[mispos]를 true로 지정 후 2번째 for문을 반복시키면서 연결시킨다.
결국 반복문을 진행하면 마을이 끊어져있지 않은이상 반복이 끝난후 dist가 전부 무한대가 아닌 일정 값 형태로 존재할 수 밖에없다.
found배열과 map배열을 통해 dist를 열심히 수정해나가는 작업 및 found를 수정하면서 지난 지점 확인체크 수정을 진행한다.
또 다시 정리
큰 for문은 점들을 한번씩 지정해 그것을 기준으로 찾고 그안의 첫번째 for문은 가장 가까운 지점을 찾아 계산을 처리하고
두번째 for문은 해당 지점과 연결된 선을 가진 애들을 찾아 dist를 수정하는 역할을 반복하여
끝내 가장 가까운 dist 배열을 찾을 수 있다.
