[4963번] 섬의 개수

#include 
#include 

using namespace std;

int w, h, x, y;
int map[51][51];
bool visited[51][51];
int cnt;
int dx[] = { 1,-1,0,0,1,-1,1,-1};
int dy[] = { 0,0,1,-1,-1,-1,1,1};
queue Q;

void input() {
        //초기화
	cnt = 0;
	for (int i = 0; i < h; i++) {
		for (int j = 0; j < w; j++) {
			cin >> map[i][j]; visited[i][j] = false;
		}
	}
}

void solve(int _qx,int _qy) {
	Q.push(_qx); Q.push(_qy); visited[_qx][_qy] = 1;

	while (!Q.empty()) {
		int qx = Q.front(); Q.pop();  int qy = Q.front(); Q.pop();

		for (int i = 0; i < 8; i++) {
			x = qx + dx[i];
			y = qy + dy[i];
			if (x >= 0 && x < h && y >= 0 && y < w && map[x][y] == 1 && !visited[x][y]) {
				visited[x][y] = 1; Q.push(x); Q.push(y);
			}
		}
	}
}

int main() {
	while (1) {
		cin >> w >> h;
		if (w == 0 && h == 0) {
			break;
		}
		input();
		for (int i = 0; i < h; i++) {
			for (int j = 0; j < w; j++) {
				if (map[i][j] == 1 && !visited[i][j]) {
					solve(i, j); cnt++;
				}
			}
		}
		cout << cnt << endl;
	}
	return 0;
}

2018.07.23 (월) 스터디 1회 BFS

이번 문제는 BFS.DFS를 사용해서 푸는 유형이었다. 주말에 삼성SDS문제를 풀 때 기억이 안 나서 꽤나 고생했던 문제였는데

이번에는 좀 더 집중을 해서 그런지 구현을 좀 더 할 수 있었다. 아쉬웠던 것은 Queue사용에 있어 아직 미숙하다는 점이다.

큰태오빠의 코드를 열심히 익혀서 내가 스스로 완벽하게 구현을 할 수 있을 때까지 노력해야겠다.