백준 4963 섬의 개수

www.acmicpc.net/problem/4963

4963번: 섬의 개수

BFS와 DFS를 연습하기에 좋은 간단한 문제였다.

주의해야 할 점이 있다면 상하좌우뿐만 아니라 대각선에도 땅이 있다면 섬으로 연결시켜줘야 한다.

 

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

int ar[51][51];
bool vis[51][51];
int dx[8] = { 0,0,1,-1,-1,1,-1,1 };
int dy[8] = { 1,-1,0,0,-1,-1,1,1 };

int main() {
	int w, h, cnt = 0;
	queue<pair<int, int>> Q;
	while (1) {
		cin >> w >> h;
		if (w == 0 && h == 0) break;
		for (int i = 0; i < h; i++) {
			for (int j = 0; j < w; j++) {
				cin >> ar[i][j];
			}
		}

		for (int i = 0; i < h; i++) {
			for (int j = 0; j < w; j++) {
				if (vis[i][j] || ar[i][j] == 0) continue;
				Q.push({ i,j }); vis[i][j] = true; cnt++;
				while (!Q.empty()) {
					auto cur = Q.front(); Q.pop();
					for (int i = 0; i < 8; i++) {
						int nx = cur.first + dx[i];
						int ny = cur.second + dy[i];
						if (nx < 0 || nx >= h || ny < 0 || ny >= w) continue;
						if (vis[nx][ny] || ar[nx][ny] == 0) continue;
						Q.push({ nx,ny }); vis[nx][ny] = true; 
					}
				}
			}
		}
		cout << cnt << '\n';
		cnt = 0;
		for (int i = 0; i < 51; i++) {
			fill(ar[i], ar[i] + 51, 0);
			fill(vis[i], vis[i] + 51, false);
		}
	}
	return 0;
}

맵을 입력 받고 땅인 것들만 큐에 넣어주고 bfs를 돌린다 끝날 때마다 초기화해주는 것을 잊지 말자.

 

#include <iostream>
using namespace std;
	
int w, h, cnt;
int ar[51][51];
bool vis[51][51];
int dx[8] = { 0,0,1,1,1,-1,-1,-1 };
int dy[8] = { 1,-1,-1,0,1,-1,0,1 };

void dfs(int x, int y) {
	vis[x][y] = true;
	for (int i = 0; i < 8; i++) {
		int nx = x + dx[i];
		int ny = y + dy[i];
		if (nx >= 0 && nx < h && ny >= 0 && ny < w) {
			if (ar[nx][ny] && !vis[nx][ny]) {
				vis[nx][ny] = true; dfs(nx, ny);
			}
		}
	}
}

int main() {
	while (1) {
		cin >> w >> h;
		if (!w && !h) break;
		for (int i = 0; i < h; i++) {
			for (int j = 0; j < w; j++) {
				cin >> ar[i][j];
			}
		}
		for (int i = 0; i < h; i++) {
			for (int j = 0; j < w; j++) {
				if (!vis[i][j] && ar[i][j]) {
					dfs(i, j); cnt++;
				}
			}
		}
		cout << cnt << '\n';
		cnt = 0;
		for (int i = 0; i < 51; i++) {
			fill(ar[i], ar[i] + 50, 0);
			fill(vis[i], vis[i] + 50, false);
		}
	}
	return 0;
}

 

dfs코드 또한 크게 다를 것 없었다.