문제
N*N의 섬나라 아일랜드의 지도가 격자판의 정보로 주어집니다. 각 섬은 1로 표시되어 상하좌 우와 대각선으로 연결되어 있으며, 0은 바다입니다. 섬나라 아일랜드에 몇 개의 섬이 있는지 구하는 프로그램을 작성하세요.
만약 위와 같다면
[입력설명]
첫 번째 줄에 자연수 N(3<=N<=20)이 주어집니다. 두 번째 줄부터 격자판 정보가 주어진다.
[출력설명]
첫 번째 줄에 섬의 개수를 출력한다.
입력예제 1
7
1100010
0110110
0100000
0001011
1101100
1000100
1010100
출력예제 1
5
문제 풀이
코드
- 이 문제는 DFS로 푼다.(다음 글에서는 같은문제를 BFS로 푼다.) DFS이기 때문에 재귀함수를 사용한다. 문제의 그림에서 섬은 5개이기 때문에, 재귀는 5번이 돈다.
- 8방향 탐색을 한다. (봉우리 문제, 미로탐색 문제 참고)
<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];
function DFS(x, y){
board[x][y]=0;
//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){
DFS(nx, ny);
}
}
}
for(let i=0; i<n; i++){
for(let j=0; j<n; j++){
if(board[i][j]===1){
answer++;
console.log(i, j); //테스트 사이트에선 디버깅 기능 없으니까, 중간중간 찍어보기
DFS(i, j);
}
}
}
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