[이것이 코딩 테스트다] 특정 거리의 도시 찾기 - 자바스크립트

문제 설명

K는 최단 거리, X는 출발 도시 일때 X번 도시에서 출발하여 도달할 수 있는 도시중, 최단 거리가 K인 도시를 구하라.
없다면 -1을 return 하라.

입력 예시

K=2, X=1

도시의 연결상태(단방향)
1 2
1 3
2 3
2 4

---

코드는 다음과 같다.

function solution(K, X, list) {
    let graph = {};
    let queue = [];
    let answer = [];
    let distance = []; //모든 도시에 대한 거리
    distance[X] = 0; //출발->출발은 0

    list.forEach(item => {
        graph[item[0]] ? graph[item[0]].push(item[1]) : graph[item[0]] = [item[1]]
    }); //그래프 전처리

    function bfs(graph, X) {
        queue.push(X); //들어온 X를 queue에 넣어준다.

        while (queue.length > 0) { //queue에 요소가 있을때까지 반복한다.
            const now = queue.shift(); //queue에서 맨 앞의 요소를 꺼낸다.

            if (!graph[now]) return; //만약 graph에서 요소key를 찾을 수 없으면 끝낸다.

            for (let next of graph[now]) { //now번 도시에서 갈 수 있는 도시 목록을 탐색
                if (distance[next] !== 1) { //X번 도시에서 한 번에 갈 수 없다면
                    distance[next] = distance[now] + 1; //이어진 도시까지의 거리를 지금도시까지의 거리 +1 해준다.
                    queue.push(next); //다음 도시를 queue에 넣어준다.
                }
            }
        }
    }

    bfs(graph, X); //처음엔 그래프와 X를 넣어서 시작한다.

    let check = false; //먼저 check변수를 만들어 false로 초기화한다.
   
    for (let i=0; i<distance.length; i++) { //거리배열을 순회하면서
        if (distance[i] === K) { //만약 최단거리로 갈 수 있는 도시가 있다면
            check = true; //check를 true로 바꾸고
            answer.push(i); //answer배열에 넣어준다.
        }
    }

    if (!check) { //만약 최단거리로 갈 수 있는 도시가 없다면
        return -1 //1을 리턴
    } else { //있다면
        return answer; //answer배열을 리턴
    }
}

solution(2, 1, [[1,2], [1,3], [2,3], [2,4]]);

BFS를 이용해야하는 문제이다.

먼저 나는 도시의 연결상태는 그냥 함수의 인자로 넣어줬다.

도시의 연결 상태를 객체 변수에 키:값 형태로 넣어주어 bfs를 진행할 수 있게 만들었다.

list.forEach(item => {
        graph[item[0]] ? graph[item[0]].push(item[1]) : graph[item[0]] = [item[1]]
    });

그래서 그래프 형태는 다음과 같다.

{ 
  '1': [ 2, 3 ], 
  '2': [ 3, 4 ] 
}

필요한 변수는 다음과 같다.

• 그래프 객체 => 초기화 해주었음
• 큐 배열
• 답 배열
• 거리를 저장할 배열 => X번에서 X번은 0이므로 [0]=0으로 초기화 해준다.

그다음 X번 도시에서 시작해야하므로 BFS의 인자로는 (그래프, X)이렇게 들어가야 할 것이다.
그렇다면 처음 도시가 들어왔을때 각 도시까지의 이동 횟수를 구해야할 것이다.

순서는 다음과 같다.

• 도시번호가 들어왔을 때 큐에 넣어준다.
• 도시로부터 갈 수 있는 도시가 없다면 반복을 끝낸다.
• 해당 도시와 연결된 도시들을 순회한다.
• 해당 도시에서 연결된 도시까지의 거리를 거리배열에 [연결된 도시번호]를 인덱스로 하여 현재도시까지의 거리 + 1을 해준다.
• 연결된 도시를 queue에 넣어준다.

2~5를 계속 반복해주면 된다.

bfs 템플릿과 정답을 보면서 코드를 분석해봤다.
처음엔 몰랐는데 글로 쓰면서 분석해보니 메커니즘을 알게 되었다.