Algorithm272 [ 자바스크립트(JavaScript) ] section09 - 6 - 섬나라아일랜드(DFS, BFS) 📍 section09 - 6 - 섬나라 아일랜드(BFS, DFS) 문제: N*N의 섬나라 아일랜드의 지도가 격자판의 정보로 주어집니다. 각 섬은 1로 표시되어 상하좌우와 대각선으로 연결되어 있으며, 0은 바다입니다. 섬나라 아일랜드에 몇 개의 섬이 있는지 구하는 프로그램을 작성하세요. 이 문제는 DFS 와 BFS탐색으로 모두 풀 수 있는 문제다. 이 방법을 이용하면 백준4963 - 섬의 개수도 한번 풀어보자! 먼저, DFS로 푸는 방법을 알아보자. visited 배열을 선언하지 않고 현재 좌표를 0으로 만든 다음에 대각선 좌표의 값이 1인 곳만 탐색한다.(이때, 재귀적으로 dfs 함수를 호출한다.) board를 돌면서 현재 좌표와 대각선 좌표까지 0이면 더 이상 탐색할 수 없으므로 다음 좌표로 넘어간다... 2021. 10. 12. [ 자바스크립트(JavaScript) ] section09 - 5 - 송아지 찾기(BFS: 상태트리탐색) 📍 section09 - 5 - 송아지 찾기(BFS: 상태트리탐색) 문제: 현수의 위치와 송아지의 위치가 수직선 상의 좌표 점으로 주어지면 현수는 현재 위치에서 송아지의 위치까지 다음과 같은 방법으로 이동한다. 송아지는 움직이지 않고 제자리에 있다. 현수는 한 번의 점프로 앞으로 1, 뒤로 1, 앞으로 5를 이동할 수 있다. 최소 몇 번의 점프로 현수가 송아지의 위치까지 갈 수 있는지 구하는 프로그램을 작성하세요. BFS를 사용하는 문제인데, 왜 BFS를 사용하는지 강의를 통해 배울 수 있었다. 결론적으로 상태 트리, 레벨 트리를 살펴보면서 깊이 우선 탐색인 DFS처럼 한 level만 끝까지 파고들며 target과 동일할 때까지 탐색하는 것이 아니라, 한 레벨에서 이동할 수 있는 좌표를 살펴보고 targ.. 2021. 10. 12. [ 자바스크립트(JavaScript) ] section09 - 4 - 이진트리 넓이우선탐색(BFS) 📍 section09 - 4 - 이진트리 넓이우선탐색(BFS) 다음과 같이 생긴 이진트리에서 BFS로 1 2 3 4 5 6 7 출력이 나와야 한다. visited 방문 배열을 선언할 필요 없이 nv>7 일 때는 더 이상 queue에 push 하지 않아도 되므로 break한다. queue에 더 이상 값이 없을 때까지 shift()한다. console.log(solution()); function solution(){ let queue = []; let answer = ""; queue.push(1); while (queue.length){ let v = queue.shift(); answer+=v+" "; for (let nv of [v*2, v*2+1]){ if (nv > 7) break; queue.p.. 2021. 10. 7. [ 자바스크립트(JavaScript) ] section09 - 3 - 경로 탐색(인접리스트) 📍 section09 - 3 - 경로 탐색(인접리스트) 방향 그래프가 주어지면 1번 정점에서 N번 정점으로 가는 모든 경로의 가지 수를 출력하는 프로그램을 작성하는 문제다. 예를 들어 1번 정점에서 5번 정점으로 가는 가지 수는 다음과 같다. 1 2 3 4 5 1 2 5 1 3 4 2 5 1 3 4 5 1 4 2 5 1 4 5 이전과 동일한 문제지만 이번에는 인접 리스트를 활용해서 푸는 문제다. 만약에 그래프를 이용한 문제에서 정점의 개수가 10,000개 이상이라면 인접리스트를 사용하자.(인접 행렬은 정점의 개수만큼 반복문을 돌아야 하기 때문에 비효율적이다.) 이 문제도 마찬가지로 DFS를 이용해서 풀 수 있다. 경로의 가짓수만 출력하는 것이 아니라 올바르게 이동했는지 알기 위해 path 변수를 추가했다.. 2021. 10. 6. [ 자바스크립트(JavaScript) ] section09 - 2 - 경로 탐색(인접행렬) 📍 section09 - 2 - 경로 탐색(인접행렬) 방향 그래프가 주어지면 1번 정점에서 N번 정점으로 가는 모든 경로의 가지 수를 출력하는 프로그램을 작성하는 문제다. 예를 들어 1번 정점에서 5번 정점으로 가는 가지 수는 다음과 같다. 1 2 3 4 5 1 2 5 1 3 4 2 5 1 3 4 5 1 4 2 5 1 4 5 이 문제는 DFS를 이용해서 풀 수 있다. 경로의 가짓수만 출력하는 것이 아니라 올바르게 이동했는지 알기 위해 path 변수를 추가했다. 2차원 배열의 graph를 선언하여 정점과 간선의 정보를 넣는다. visited 배열을 선언하여 이미 지나온 곳은 건너뛰고 진행한다. DFS의 종료 조건은 v가 n과 같을 때이다. 인접 행렬이므로 반복문으로 모든 정점을 탐색해야 한다. DFS 함수.. 2021. 10. 6. 이전 1 2 3 4 5 6 7 8 ··· 55 다음
