[성실코딩 4일차] 백준 #4963 섬의 개수

쉬운데 왜 정답률 48%인지 모루겠움

DFS, BFS의 전형적인 문제

올해 하반히 포스코ICT SW역량평가에서 이거랑 유사하지만 응용해서 섬의 둘레 구하기 문제 나왔었음!! 

#include<iostream>

using namespace std;

int map[51][51] = {0,};
int w, h; //너비, 높이
int cnt; // 섬의 개수

int dy[8] = {-1,0,1,-1,1,-1,0,1}; // 좌상대각선, 상, 우상대각선, 좌, 우, 좌하대각선, 하, 우하대각선
int dx[8] = {-1,-1,-1,0,0,1,1,1};

void dfs(int _x, int _y) {
	// 방문 표시
	map[_x][_y] = 2;

	for (int i = 0; i < 8; i++) {
		// map 경게선을 넘어설 경우
		if ( (_x+dx[i]<0 || _x+dx[i]>=h) || 
			(_y+dy[i]<0 || _y+dy[i]>=w)) {
			continue;
		}
		else {
			if (map[_x + dx[i]][_y + dy[i]]==1) {
				dfs(_x + dx[i],_y + dy[i]);
			}
		}
	}
}

int main(void) {

	while (1) {
		//초기화
		cnt = 0;

		// 입력 받기
		cin >> w >> h;
		if (w==0 && h==0) {
			break;
		}
		for (int j = 0; j < h; j++) {
			for (int k = 0; k < w; k++) {
				cin >> map[j][k];
			}
		}

		// dfs 처리
		for (int j = 0; j < h; j++) {
			for (int k = 0; k < w; k++) {
				if (map[j][k]==1) { // 땅
					cnt++;
					dfs(j,k);
				}
			}
		}
		cout << cnt << endl;
	}
	
	
	return 0;
}