87. 섬나라 아일랜드(BFS)

문제

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

입력설명

첫 번째 줄에 자연수 N(1<=N<=20)이 주어집니다. 두 번째 줄부터 격자판 정보가 주어진다.

출력설명

첫 번째 줄에 섬의 개수를 출력한다.

입력예제

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

---

#include <stdio.h>
#include <vector>
#include <queue>
using namespace std;
int n, map[30][30], count=0;
int dx[8] = {0, 1, 1, 1, 0, -1, -1, -1};
int dy[8] = {-1, -1, 0, 1, 1, 1, 0, -1};
struct Location{
	int x;
	int y;
	Location(int a, int b){
		x = a;
		y = b;
	}
};
queue<Location> Q;

int main(){
	//freopen("input.txt", "rt", stdin);
	int i, j;
	scanf("%d", &n);
	for(i=1; i<=n; i++){
		for(j=1; j<=n; j++){
			scanf("%d", &map[i][j]);
		}
	}
	
	for(i=1; i<=n; i++){
		for(j=1; j<=n; j++){
			if(map[i][j] == 1){
				Q.push(Location(i, j));
				map[i][j] = 0;
				while(!Q.empty()){
					Location temp = Q.front();
					Q.pop();
					for(int i=0; i<8; i++){
						if(map[temp.x + dx[i]][temp.y + dy[i]] == 1){
							Q.push(Location(temp.x + dx[i], temp.y + dy[i]));
							map[temp.x + dx[i]][temp.y + dy[i]] = 0;
						}
					}
				}
				count++;
			}
		}
	}
	printf("%d", count);
	
	return 0;
}

상하좌우 대각선까지 포함해서 1이있으면 하나의 섬으로 칩니다

DFS, BFS풀면서 점점 말이 없어지네요. 너무 어렵워 - ! ! !

한번 탐색한건 0으로두고 섬 개수를 카운트하고 섬이끝낫을때는 멈췃던 2차원배열 탐색을 재개합니다