[C++ / 백준 4963번] 섬의 개수

문제

 

시행 착오

 

fill 2차원 배열 초기화에 관해 이슈가 있었다.

 

fill 의 두 번째 파라미터는 끝 주소를 포함하지 않기 때문에 끝 주소 + 1 을 해 주어야 올바르게 초기화가 되었다.

 

해결 방법

 

DFS를 이용해 범위 내에서 문제 조건에 따라 순회 해 주었다. DFS 가 끝날 때마다 cnt+1 을 시행했다.

재방문은 그대로 리턴하도록 하였다.

 

#include <iostream>


using namespace std;

bool visited[50][50] = { false };
int map[50][50]; 
int cnt = 0;
int w, h;


void dfs(int y, int x)
{
	if (visited[y][x]) return;
	if (y < 0 || y >= h || x < 0 || x >= w) return;

	visited[y][x] = true;

	if (map[y + 1][x] == 1)  dfs(y + 1, x);
	if (map[y - 1][x] == 1) dfs(y - 1, x);
	if (map[y][x + 1] == 1) dfs(y, x + 1);
	if (map[y][x - 1] == 1) dfs(y, x - 1);
	if (map[y+1][x + 1] == 1) dfs(y + 1, x + 1);
	if (map[y+1][x - 1] == 1) dfs(y+1, x - 1);
	if (map[y - 1][x + 1] == 1) dfs(y - 1, x + 1);
	if (map[y - 1][x - 1] == 1) dfs(y - 1, x - 1);
	

	return;
}

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

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

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

		for (int i = 0; i < h; i++)
		{
			for (int j = 0; j < w; j++)
			{
				if (map[i][j] == 1 && !visited[i][j])
				{
					dfs(i, j);
					cnt += 1;
				}

			}
		}

		cout << cnt << '\n';

		fill(&map[0][0], &map[49][50], 0);
		fill(&visited[0][0], &visited[49][50], false);

	}



	return 0; 
}