4963번 섬의 개수

 

4963번: 섬의 개수

오랜만에 BFS 문제를 풀어봤다. 

 

요즘은 소마 코테를 준비하느라 브루트포스, DP, BFS 위주로 푸는 중이다.

 

각설하고, 입력된 그래프의 연결요소의 개수를 구하는 문제.

 

연결 요소란, '무향 그래프에서 서로 다른 두 정점이 경로로 연결되어 있으면서 상위 그래프의 추가 정점이 없는 부분 그래프'라고 한다.

그림으로 보면 G라는 그래프에 연결요소는 H0, H1 총 2개가 있는 것이다.

 

이 문제를 푸는데에 고려한 부분은

 

"연결상태를 어떻게 저장할까?" 라는 것이었다.

 

2차원 배열에 저장하자니 x, y 좌표 두 개를 동시에 저장할 수가 없다. 

 

해법은 queue<pair<int x,int y>>로 저장하는 것. 

 

큐가 텅 빌때까지 루프를 시켜주도록 한다.

 

#include <iostream>
#include <cstring>
#include <queue>
using namespace std;

queue<pair<int,int>> que;
int map[51][51];
bool visited[51][51];
int dir[8][2] = { {-1,0},{-1,1},{0,1},{1,1},{1,0},{1,-1},{0,-1},{-1,-1} };
int w, h;
int result;

void bfs(int x, int y) {
	int curr_x, curr_y;
	visited[x][y] = true;
	que.push(make_pair(x, y));
	while (!que.empty()) {
		for (int i = 0; i < que.size(); i++) {
			int curr_x = que.front().first; int curr_y = que.front().second;
			que.pop();
			for (int k = 0; k < 8; k++) {
				int dir_x = curr_x + dir[k][0]; int dir_y = curr_y + dir[k][1];
				if (0 <= dir_x && dir_x < h && 0 <= dir_y && dir_y < w) {
					if (!visited[dir_x][dir_y] && map[dir_x][dir_y] == 1) {
						visited[dir_x][dir_y] = true;
						que.push(make_pair(dir_x, dir_y));
					}
				}
			}
		}
	}
	result++;
}

int main() {
	while (true) {
		memset(map, 0, sizeof(map));
		memset(visited, false, sizeof(visited));
		result = 0;
		cin >> w >> h;
		if (!w && !h)break;
		for (int i = 0; i < h; i++) {
			for (int j = 0; j < w; j++) {
				cin >> map[i][j];
			}
		}

		for (int i = 0; i < h; i++) {
			for (int j = 0; j < w; j++) {
				if (map[i][j] && !visited[i][j]) {
					bfs(i, j);
					
				}
			}
		}
		cout << result << "\n";
	}
	return 0;
}