백준 js 18352번

 

<문제2>

다익스트라 알고리즘 문제

https://www.acmicpc.net/problem/18352

 

 

 

<문제 핵심>

 

1.  단방향 그래프

✅ 2차원 배열로 만들어진 graph에 grph[from].push(to) 적용하여 단방향 그래프를 완성할 수 있냐

 

2.  BFS 알고리즘 활용

✅ 입력으로 받은 x를 bfs(x)로 호출. bfs 함수를 구현할 수 있냐

 

 

<자료구조/알고리즘>

 

1. BFS(너비 우선 탐색) 알고리즘

✅ 그래프에서 최단 거리를 구하는데 적합한 알고리즘

✅ 시작 정점에서부터 인접한 정점들을 먼저 탐색하는 방식으로 '큐' 자료구조를 이용하여 구현할 수 있다.

 

2. 그래프 탐색

✅ 인접 리스트 방식을 이용하여 각 정점에 연결된 다른 정점들을 리스트로 표현

 

 

<해결방법 및 순서도>

 

1.  n~k까지 입력 받고 도로 정보가 담긴 배열 arr과 인접리스트 기반의 그래프 그리고 도로의 거리를 카운트 하여 방문 체크에 이용할 배열을 생성한다. 

✅distances 배열같은 경우 0번 인덱스를 사용하지 않는다.

let input = require("fs").readFileSync(0, "utf-8").toString().split("\n");

let [n, m, k, x] = input.shift().split(" ").map(Number);
const arr = input.map((v) => v.split(' ').map(Number));
const graph = Array.from({ length: n + 1 }, () => []);
const distances = Array(n + 1).fill(0); // 도로의 거리를 카운트하면서 방문 체크에 이용할 배열
let answer = [];

 

 

2. 단방향 그래프 초기화 및 bfs 함수 로직 구현

✅ forEach문을 통해 단방향 그래프 완성

✅ queue를 사용하여 탐색할 도시를 저장하고, 출발 도시의 거리를 1로 설정한다. 

ex. start가 1일 경우 distances = [0, 1, 0, 0, 0]

✅ 큐가 없을 때 까지 while문 진행하고 큐에서 도시를 하나씩 꺼내 현재 도시의 거리가 k + 1이면 answer 배열에 추가

✅ 현재 도시와 연결된 모든 도시에 대해 아직 방문하지 않은 도시를 큐에 추가하고, 거리를 갱신

-> 즉 distances 배열에서 next에 해당하는 요소가 false 이면 큐에 추가. 그리고 next 요소에 해당하는 거리에 기존 now 요소의 거리 + 1 해준다.

arr.forEach(([from, to]) => graph[from].push(to));

const bfs = (start) => {
  const queue = [start];
  distances[start] = 1;

  while (queue.length) {
    const now = queue.shift();
    if (distances[now] == k + 1) {
      answer.push(now);
      continue;
    }
    for (const next of graph[now]) {
      if (!distances[next]) {
        queue.push(next);
        distances[next] = distances[now] + 1;
      }
    }
  }
};

bfs(x);

 

 

3. 최종 결과 확인

✅ BFS 탐색을 마친 후 answer 배열에 K 거리에 해당하는 도시가 있으면 오름차순으로 정렬하고 배열에 줄바꿈 적용하며 출력

✅ answer 배열이 비어 있으면 -1을 출력

 

if (answer.length) {
  answer = answer.sort((a, b) => a - b).join('\n');
} else {
  answer = -1;
}

console.log(answer);

 

 

 

<6월 4일 자 수정된 코드>

스터디 팀원들과 코드에 대해서 공유하는 시간을 가졌는데 distances 배열을 0으로 초기화 할 경우 시작 노드의 거리를 갱신 해줄 때 가독성이 떨어지는 단점이 있다는 내용을 들었다. 그래서 배열의 초기값을 Infinity로 설정해주고(매우 큰 숫자 이므로 이후 0으로 세팅해줄 때 가독성이 용이해짐) bfs 함수를 호출하여 시작 노드의 거리를 0으로 세팅해주는 로직으로 바꿔보았다!

 

https://github.com/Jayjunyoung/Algorithm_Practice/commit/c3e55a23cd895476af4fa86b252e3be552f04443

백준 18352번 다시 풀이 · Jayjunyoung/Algorithm_Practice@c3e55a2