문제
문제 풀이
예습이론
이 문제는 BFS(넓이우선탐색)의 개념을 알아보는 문제이다. BFS의 개념은 앞장에서 정리했으니 참고하기!
간단히 BFS에 대한 설명을 하자면,
- 큐를 사용한다(FIFO)
- level을 사용한다.
- 최단거리를 구할 때 사용한다.(1 level에서 가까운 순서대로 출력)
- 상태트리를 사용한다. 원리는 다음과 같다
- BFS의 알고리즘
*시작노드를 큐에 삽입하며 시작 + 방문처리 (이후 아래과정 반복)
(1) 큐에서 하나의 노드를 꺼낸다.
(2) 해당 노드에 연결된 노드 중, 방문하지 않은 노드를 방문하고 차례대로 큐에 삽입 후 방문처리한다.
코드
<html>
<head>
<meta charset="UTF-8">
<title>출력결과</title>
</head>
<body>
<script>
function solution(){
let answer=""; //string
let queue=[]; //큐 배열 만듦
queue.push(1); //루트노드 1번 넣어줌
//queue.length===0이면 비어있다는 소리니까 while문 멈추게 됨
while(queue.length){
let v=queue.shift(); //큐에서 하나의 노드(v) 꺼냄
answer+=v+" ";
//v의 이웃노드 방문
//nv: next v, nv는 for문에 의해 v*2, v*2+1이 됨
for(let nv of [v*2, v*2+1]){
if(nv>7) continue; //아래 코드 건너뜀(7이상은 안들어감)
queue.push(nv); //(위에서 꺼낸 노드에 연결된 노드중, 방문하지 않은 노드 큐에 삽입
}
}
return answer;
}
console.log(solution());
</script>
</body>
</html>
내가 짱이다 😎 매일 조금씩 성장하기🌱
9/18
bfs의 알고리즘 외우기