문제
앞의 문제(9-7)와 동일
문제 풀이
코드
9-7과 같은 문제를 BFS를 활용해서 풀이한다. 원리는 다음과 같다.
<html>
<head>
<meta charset="UTF-8">
<title>출력결과</title>
</head>
<body>
<script>
function solution(board){
let answer=0;
let n=board.length;
let dx=[-1, -1, 0, 1, 1, 1, 0, -1];
let dy=[0, 1, 1, 1, 0, -1, -1, -1];
let queue=[]; //큐 배열 생성
for(let i=0; i<n; i++){
for(let j=0; j<n; j++){
//섬이라면
if(board[i][j]===1){
board[i][j]=0; //바다로 만듦(check)
queue.push([i, j]);
answer++; //섬 카운팅(1을 발견하면 섬을 발견한것과 같다!)
//queue.length===0이 되면 멈춤
while(queue.length){
let [x, y]=queue.shift(); //[x, y] 꺼내서, [x, y]와 연결된 좌표 봄(8방향 탐색 통해)
console.log(x, y); //test
//[x,y]의 이웃을 찾음(8방향 좌표)
for(let k=0; k<8; k++){
let nx=x+dx[k];
let ny=y+dy[k];
if(nx>=0 && nx<n&& ny>=0 && ny<n && board[nx][ny]===1){
board[nx][ny]=0;
queue.push([nx, ny]);
}
}
}
console.log("BFS end")
}
}
}
return answer;
}
let arr=[[1, 1, 0, 0, 0, 1, 0],
[0, 1, 1, 0, 1, 1, 0],
[0, 1, 0, 0, 0, 0, 0],
[0, 0, 0, 1, 0, 1, 1],
[1, 1, 0, 1, 1, 0, 0],
[1, 0, 0, 0, 1, 0, 0],
[1, 0, 1, 0, 1, 0, 0]];
console.log(solution(arr));
</script>
</body>
</html>출력 결과
내가 짱이다 😎 매일 조금씩 성장하기🌱
9/18
앞문제 풀이와 비교해보기