백준 4963. 섬의 개수[성공]

1.문제 해결 전략

이전 문제를 통해 연결 요소에 대한 문제의 해결 방법을 알고있었기 때문에 접근하기 쉬웠다. 인접한 노드의 기준이 8방향인 것을 제외하면 이전 문제와 거의 일치한다. 

 

2.작성 코드

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

int DirX[8] = { -1,-1,0,1,1,1,0,-1 };
int DirY[8] = { 0,1,1,1,0,-1,-1,-1 };
bool bVisit[50][50] = { false, };
int input[50][50];
int cnt = 0;
int w, h;
void dfs(int x, int y) {

	bVisit[y][x] = true;
	for (int i = 0; i < 8; i++) {
		int dirx = x + DirX[i];
		int diry = y + DirY[i];

		if (dirx >= 0 && dirx < w && diry >= 0 && diry < h && !bVisit[diry][dirx] && input[diry][dirx] ==1)dfs(dirx, diry);
	}

}


int main() {

	while(true){
		memset(bVisit, false, sizeof(bVisit));
		memset(input, 0, sizeof(input));
		cin >> w >> h;
		if (w == 0 && h == 0)break;

		for (int i = 0; i < h; i++)
			for (int j = 0; j < w; j++)
				cin >> input[i][j];

		for(int i =0; i<h;i++)
			for (int j = 0; j < w; j++)
			{
				if (input[i][j] == 1 && bVisit[i][j] == false) {
					dfs(j,i);
					cnt++;
				}
			}
		
		cout << cnt << endl;
		cnt = 0;
	}
	
	return 0;
}

3.걸린 시간 & 느낀점

의외로 30분 가까이 시간을 허비했다. 이전 문제와 다르지 않다는 점을 고려하면 굉장히 오래걸린 시간인데 그 이유는 x,y 좌표를 배열에 잘못 넣고있었기 때문이다. x,y 값을 받아올 때 2중 포문을 통해 width/height 만큼 반복하게 되는데 x,y 와 height/width 짝맞춤으로 돌리고 있어서 테스트 케이스중 하나가 일치하지 않아 시간을 잡아먹었었다.

 

연결요소는 카카오톡 인턴 문제로도 나왔었는데 그 때는 그래프 단원 공부를 해보지 않았었기에 접근조차 못했었다. 앞으로 남은 문제들을 통해 dfs,bfs 만큼은 확실히 배워서 응용할 수 있도록 만들어야겠다.