[백준/c++] 4963 섬의 개수

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

 

전형적인 dfs 문제인 것 같지만 조금 생각을 해야하는 문제인가..? 일단 나한테는 그럼..

 

dfs 함수가 있고, main함수 안에 dfs 함수 꼴이 있는데 둘은 차이가 있다. 

1. dfs 함수는 시작점을 찾은 후 섬을 만드는 과정

2. main함수의 2중 for문은 시작점을 찾는 과정이다.

 

여러개를 받아서 dfs를 구해야하기 때문에 reset이 필수적이다. 

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

int map[51][51];
bool isVisited[51][51] = { false };
//상하좌우 + 대각선
int dx[8] = { -1,0,1,1,1,0,-1,-1 };
int dy[8] = { 1,1,1,0,-1,-1,-1,0 };
int n, m;


//isVisited, map 초기화
void reset() {
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			isVisited[i][j] = false;
			map[i][j] = 0;
		}
	}
}

//dfs
void dfs(int x, int y) {
	for (int i = 0; i < 8; i++) {
		int nx = x + dx[i];
		int ny = y + dy[i];

		if (nx >= 0 && ny >= 0 && nx < n && ny < m) {
			if (!isVisited[nx][ny] && map[nx][ny]==1) {
				isVisited[nx][ny] = true;
				dfs(nx, ny);
			}
		}
	}
}
int main() {
	while (1) {
		int cnt = 0;
		cin >> m >> n;
		if (n == 0 && m == 0) {
			break;
		}
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				cin >> map[i][j];
			}
		}
		//시작지점 찾기
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				if (!isVisited[i][j] && map[i][j] == 1) {
					isVisited[i][j] = true;
					dfs(i, j);
					cnt++;
				}
			}
		}
		cout << cnt << endl;
		reset();
	}
}