[백준 BOJ] 4963 : 섬의 개수 (C++)

https://www.acmicpc.net/problem/4963

4963번: 섬의 개수

아이디어 흐름

1. 아이디어 구상

1. 해당 위치에서 주변으로 뻗어나가는 탐색이 필요 => DFS, BFS 모두 가능할 것 같다.
2. 가로, 세로, 대각선 모두 연결을 확인해야 하므로 탐색은
dx = { 1, 1, 0, -1, -1, -1, 0, 1 }
dy = { 0, 1, 1, 1, 0, -1, -1, -1 }
dx[i], dy[i] 인덱스를 이동시키는 방식으로 상하좌우 대각선 탐색 (탐색에 dfs, bfs 이용)
3. cnt를 선언하여, main에서 for문을 통해 그래프 탐색을 호출할 때마다 cnt를 늘려주는 방식으로 진행

2. 초기 아이디어의 한계, 수정

dy, dx 배열의 인덱스를 이동시키며 현재 노드에서 상하좌우, 대각선 탐색하는 문제를 풀어본 경험이 있다면 아이디어를 떠올리는 것 자체는 어렵지 않게 할 수 있는 문제였다.

3. 코드

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

int h, w;
int graph[51][51];
bool visited[51][51];
int dy[8] = { 0, 1, 1, 1, 0, -1, -1, -1 };
int dx[8] = { 1, 1, 0, -1, -1, -1, 0, 1 };
// 차례대로 우, 우하, 하, 좌하, 좌, 좌상, 상, 우상

// 1. 해당 노드 방문처리
// 2. 해당 노드로부터 상하좌우, 대각선으로 해당 노드가 인덱스를 벗어나지 않고, 
//    !visited이고 1이라면 해당 노드 dfs재귀호출

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

void bfs(int y, int x) {
	queue <pair<int, int>> q;
	q.push(make_pair(y, x));
	visited[y][x] = true;
	while (!q.empty()) {
		int y = q.front().first;
		int x = q.front().second;
		q.pop();
		for (int i = 0; i < 8; i++) {
			int ny = y + dy[i];
			int nx = x + dx[i];
			if ((ny >= 0 && ny < h) && (nx >= 0 && nx < w) && (graph[ny][nx] == 1) && (!visited[ny][nx])) {
				visited[ny][nx] = true;
				q.push(make_pair(ny, nx));
			}
		}
	}
}

int main() {
	while (1) {
		int answer = 0;
		cin >> w >> h;

		if (w == 0 && h == 0) break;

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

		for (int i = 0; i < h; i++) {
			for (int j = 0; j < w; j++) {
				if (!visited[i][j] && graph[i][j] == 1) {
					//dfs(i, j);
					bfs(i, j);
					answer++;
				}
			}
		}
		cout << answer << '\n';
		memset(visited, 0, sizeof(visited));
	}
}

4. 아쉬운점

• 총 소요 시간 : 1시간 10분...
• 아이디어 구상 : 10분
• 코드 작성 : 30분
• 디버깅 : 30분

아이디어를 구상할 때도 그렇고, 문제를 해결한 후에도 그렇고 뭔가 크게 어렵거나 복잡한 부분이 없는데, 구현력이 부족한 이유인지 40분 정도에 걸쳐 dfs, bfs까지 전부 작성해놓고는 사소한 실수들, 오류들을 해결하는 디버깅에 30분이나 소요되었다....문제를 훨씬 더 많이 풀고 실수를 줄이도록 노력해야겠다.