섬나라 아일랜드(BFS) / c++ / 제한시간 없음

▣ 문제

섬나라 아일랜드의 지도가 격자판의 정보로 주어집니다. 각 섬은 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

 

<코드>

#pragma warning(disable:4996)
#include<stdio.h>
#include<queue>
#include<algorithm>
using namespace std;

struct cur {
	int x;
	int y;
	cur(int a, int b) {
		x = a;
		y = b;
	}
};
int map[21][21];
int dx[8] = { 0,1,1,1,0,-1,-1,-1 };
int dy[8] = { -1,-1,0,1,1,1,0,-1 };
int n;

int main() {
	int i, j, cnt = 0;
	scanf("%d", &n);
	for (i = 1; i <= n; i++) {
		for (j = 1; j <= n; j++) {
			scanf("%d", &map[i][j]);
		}
	}
	queue<cur> Q;
	for (i = 1; i <= n; i++) {
		for (j = 1; j <=n ; j++) {
			if (map[i][j] == 1) {
				Q.push(cur(i, j));
				map[i][j] = 0;
				while (!Q.empty()) {
					cur temp = Q.front();
					Q.pop();
					for (int k = 0; k < 8; k++) {
						int xx, yy;
						xx = temp.x + dx[k];
						yy = temp.y + dy[k];
						if (map[xx][yy] == 1) {
							Q.push(cur(xx, yy));
							map[xx][yy] = 0;
						}
					}
				}
				cnt++;
			}
		}
	}
	printf("%d\n", cnt);
	return 0;
}

map[ ][ ] 전체를 탐색하면서 1이 발견되면 큐(Queue)를 활용해 BFS를 사용한다. while문이 끝날떄마다 cnt++을 해준다.

 

.

 

비교적 간단한 예시의 BFS

 

구조체(Struct)를 사용하는법에 좀 더 익숙해져야 할듯