[백준] 14442번, 벽 부수고 이동하기 2 (JavaScript)

Algorithm

📌 문제 정보 : 벽 부수고 이동하기 2

• 문제 분류 : 자료 구조, 그래프 이론, 그래프 탐색, 너비 우선 탐색
• 문제 출처 : 백준 골드 3, 벽 부수고 이동하기 2

✅ 접근 과정

이 문제는 이전 벽 부수고 이동하기에서 벽을 부수는 횟수가 K(1 <= K <= 10)번까지로 추가된 버전이다.

벽은 부수는 횟수를 카운트하기 위해 기존 방문 배열을 3차원으로 확장하여 최대 K번까지 벽을 부수면서 목표 지점에 도달할 수 있는지를 확인하면 된다.

마지막으로 방문 배열의 [N][N]에서 1부터 K개 까지의 벽을 부수고 도달 가능한 횟수들 중 가장 작은 값을 출력하면 된다.

유용했던 정보 : 이 문제의 경우 기존 BFS 문제들과 다르게 JavaScript의 경우, 큐(Queue)를 직접 구현해야만 시간 제한을 통과할 수 있는 문제이다.

✨ 풀이 코드

• 큐 클래스 구글링을 통해 가져왔는데.. 출처를 잘 모르겠습니다..ㅠㅠ

🚩 마치며

BFS 문제를 풀 때 항상 큐를 직접 구현하지 않고 배열의 Array.shift()를 사용했었다. 이렇게 하면 최악의 경우 큐의 길이 만큼의 시간이 O(n)을 손해 본다는 문제점이 있지만 다른 BFS 문제 풀이에 있어서 문제가 없었기에 구현을 다 하고도 시간초과의 원인을 찾느라 시간을 많이 허비했다..

JS에도 빨리 큐와 우선순위 큐 등 부족한 자료형들이 추가되었으면 좋겠다..