BFS

📌 07 - 섬나라 아일랜드(BFS 활용) N*N의 섬나라 아일랜드의 지도가 격자판의 정보로 주어진다. 각 섬은 1로 표시되어 상하좌우와 대각선으로 연결되어 있으며, 0은 바다이다. 섬나라 아일랜드에 몇 개의 섬이 있는지 구하는 문제이다. 만약 위와 같다면 섬의 개수는 총 5개이다. 섬나라 아일랜드(DFS) 문제와 같지만 이번에는 BFS 알고리즘을 이용해 풀어보았다. 영역을 탐색하는 문제의 경우에는 본인에게 편한 방법을 이용하여 풀면 될 것 같다..🤔 📝 풀이 방법 이중 for 문을 돌면서 1이 나온다면 섬을 발견한 것이므로 배열에서 해당 좌표를 0으로 재할당하고 answer++을 한다. 또한, 넓이 우선 탐색을 위해 큐에 해당 좌표를 추가한다. while 문을 돌면서 큐에서 shift 한 좌표에 대해 ..

📌 05 - 송아지 찾기(BFS : 상대트리탐색) 현수는 송아지를 잃어버렸다. 다행히 송아지에는 위치추적기가 달려 있다. 현수의 위치와 송아지의 위치가 수직선상의 좌표 점으로 주어지면 현수는 현재 위치에서 송아지의 위치까지 다음과 같은 방법으로 이동한다. 송아지는 움직이지 않고 제자리에 있다. 현수는 스카이 콩콩을 타고 가는데 한 번의 점프로 앞으로 1, 뒤로 1, 앞으로 5를 이동할 수 있다. 최소 몇 번의 점프로 현수가 송아지의 위치까지 갈 수 있는지 구하는 문제이다. 📍 입력설명 첫 번째 줄에 현수의 위치 S와 송아지의 위치 E가 주어진다. 직선의 좌표 점은 1부터 10,000까지이다. 📍 출력설명 점프의 최소횟수를 구한다. 답은 1 이상이다. 문제를 해석하면 현수의 위치(출발 지점)에서 송아지의 ..

📌 04 - 이진트리 넓이우선탐색(BFS) 아래 그림과 같은 이진트리를 넓이우선탐색 하는 문제이다. 넓이우선탐색 : 1 2 3 4 5 6 7 언제 BFS를 사용하는가❓ 출발 지점에서 도착 지점까지의 최단 거리를 구할 때 노드 1이 출발 지점이므로 큐에 1을 추가한다. 큐가 모두 비워질 때 까지 while 문을 돌며 큐에서 shift 한 노드와 근접한 노드가 7보다 작거나 같으면 큐에 추가한다. 7보다 크다면 큐에 추가하지 않고 넘어간다. function solution() { let answer = ''; let queue = []; queue.push(1); while (queue.length) { let v = queue.shift(); answer += v + ' '; for (let nv of [..