IF - 섬나라 아일랜드

문제

N*N의 섬나라 아일랜드의 지도가 격자판의 정보로 주어집니다. 각 섬은 1로 표시되어 상하좌
우와 대각선으로 연결되어 있으며, 0은 바다입니다. 섬나라 아일랜드에 몇 개의 섬이 있는지
구하는 프로그램을 작성하세요.

예시

입력
7
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

출력
5

풀이

• 주어진 이차원 배열을 순회하면서 원소가 1 일 때만 DFS 혹은 BFS 알고리즘으로 1이 끊기는 지점까지를 섬으로 간주한다.
• 이미 지나온 칸은 다시 방문할 수 없게끔 원소를 0으로 바꾼다.
• 각 칸에서 다음 칸으로 넘어갈 수 있는 경우는 x 축으로 [0, 1, 1, 1, 0, -1, -1, -1] , y 축으로 [1, 1, 0, -1, -1, -1, 0, 1] 가 있다. (시계방향)
• x, y 축 각 방향으로 이동했을 시의 좌표가 주어진 이차원배열 내부이면서, 원소가 1인 경우에만 DFS 혹은 BFS로 탐색을 계속한다.
• 위 조건에서 더이상 이동할 좌표가 없다면, DFS 혹은 BFS를 빠져나와 처음에 돌던 이차원배열을 다시 순회하며 원소가 1인 칸을 찾는다.
• DFS나 BFS 로 하나의 섬을 파는 방법은 알았는데, 다른 섬으로 이동하는 방법을 몰라서 많이 헤맸다.. 이차원배열이니 이중for문으로 돌면 되는 간단한 해결책이 있었다.

코드 (DFS)

const solution = (board) => {
	let island = 0;
	const N = board.length;
	const dx = [0, 1, 1, 1, 0, -1, -1, -1];
	const dy = [1, 1, 0, -1, -1, -1, 0, 1];

	const DFS = (x, y) => {
		board[x][y] = 0;
		for (let k = 0; k < 8; k++) {
			const nx = x + dx[k];
			const 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) {
				island++;
				DFS(i, j);
			}
		}
	}

	return island;
};

코드 (BFS)

const solution = (board) => {
	let island = 0;
	const N = board.length;
	const dx = [0, 1, 1, 1, 0, -1, -1, -1];
	const dy = [1, 1, 0, -1, -1, -1, 0, 1];
	for (let i = 0; i < N; i++) {
		for (let j = 0; j < N; j++) {
			const queue = [];
			if (board[i][j] === 1) {
				board[i][j] = 0;
				island++;
				queue.push([i, j]);
				while (queue.length) {
					const cur = queue.shift();
					board[cur[0]][cur[1]] = 0;
					for (let k = 0; k < 8; k++) {
						const nx = cur[0] + dx[k];
						const ny = cur[1] + dy[k];
						if (nx >= 0 && nx < N && ny >= 0 && ny < N && board[nx][ny] === 1) {
							queue.push([nx, ny]);
						}
					}
				}
			}
		}
	}

	return island;
};