백준4963 - 섬의 개수

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

4963번: 섬의 개수

dfs 기본 문제이다. 

현재 있는 곳이 땅이면 8방향으로 움직이는데 8방향 중 어느 특정한 방향이 2차원 배열을 벗어나지 않고 방문하지 않은 땅이면 그 곳으로 이동하여 다시 탐색을 시작한다. 8방향 중 어떤 방향으로 이동하여도 방문하지 않은 땅이 없는 경우 전에 탐색하였던 곳으로 거슬러 올라간다. 이런 반복을 거쳐 섬의 갯수를 찾는다. 

8방향으로 이동하는 의미

 

또 주의해야 될 점은 2차원 배열을 사용할 때 첫번째 인덱스가 x, 두번째 인덱스가 y 혹은 첫번째 인덱스가 y, 두번째 인덱스가 x인지 결정해야 된다는 것이다. 그래야 반복문을 돌릴 때 오류가 안난다. 나는 첫번째 인덱스를 y로, 두번째 인덱스를 x로 설정하였다. 첫번째 반복문에서 y값을 증가, 두번째 반복문에서 x값을 증가시켰다. 

 

#include <iostream>
#include <string.h>
using namespace std;

//땅은 1, 바다는 0

int N, M; //N은 y, M은 x
int mat[50][50]; //땅과 바다의 정보를 담을 공간
bool check[50][50]; //방문한 여부를 담는 공간

//내가 있는 위치에서 총 여덟 방향으로 이동한다.
int dx[] = { -1,1,0,0,1,1,-1,-1 };
int dy[] = { 0,0,1,-1,1,-1,-1,1 };

//dfs를 통해 섬의 위치를 찾는다.
void dfs(int a, int b) {
	check[a][b] = true; //현재 탐색한 곳을 방문처리
	for (int i = 0; i < 8; i++) { //8방향으로 움직이는 동안
		int x = a + dx[i]; //이동한 곳의 x좌표
		int y = b + dy[i]; //이동한 곳의  y좌표 
		if (0 <= x && x < M && 0 <= y && y < N && mat[x][y] == 1 && !check[x][y]) { //x, y가 행렬 범위안에 있고 방문하지 않았으며 땅이면
			dfs(x, y); //그 위치부터 dfs를 시작
		}
	}
}

int main() {
	while (1) {
		int cnt = 0;
		cin >> N >> M; //y축 길이와 x축 길이 입력, M * N행렬을 구현한다.
		if (N == 0 && M == 0) { //0 두개 입력이면 종료
			break;
		}

		//섬인지 바다인지 입력
		for (int i = 0; i < M; i++) {
			for (int j = 0; j < N; j++) {
				cin >> mat[i][j];
			}
		}
		for (int i = 0; i < M; i++) {
			for (int j = 0; j < N; j++) {
				if (!check[i][j] && mat[i][j] == 1) { //내가 현재 있는 곳이 방문하지 않은 곳이며 땅이면
					dfs(i, j); //dfs시작
					cnt++; //섬의 갯수 늘리기
				}
			}
		}
		cout << cnt << '\n';
		memset(mat, 0, sizeof(mat)); //섬과 바다의 정보를 0으로 초기화
		memset(check, false, sizeof(check)); //방문 여부를 false로 초기화
	}
}