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

 

#include <iostream>

using namespace std;

void DFS(int a, int b, int row, int col);

int arr[51][51];

int main(void)
{
	cin.tie(NULL);
	ios::sync_with_stdio(false);
	
	while(true)
	{
		int num1=0;
		int num2=0;
		
		cin>>num1>>num2;
		
		if(num1==0&&num2==0)
		{
			break;
		}
		
		for(int i=0; i<num2; i++)
		{
			for(int j=0; j<num1; j++)
			{
				cin>>arr[i][j];
			}
		}
		
		int count=0;
		
		for(int i=0; i<num2; i++)
		{
			for(int j=0; j<num1; j++)
			{
				if(arr[i][j]==1)
				{
					arr[i][j]=0;
					DFS(i, j, num2, num1);
					count++;
				}
			}
		}
		cout<<count<<endl;
		
		for(int i=0; i<num2; i++)
		{
			for(int j=0; j<num1; j++)
			{
				arr[i][j]=0;
			}
		}
	}
	return 0;
}

void DFS(int a, int b, int row, int col)
{
	for(int i=-1; i<2; i++)
	{
		for(int j=-1; j<2; j++)
		{
			if(arr[a+i][b+j]==1&&a+i>-1&&a+i<row&& b+j>-1&& b+j<col)
			{
				arr[a+i][b+j]=0;
				DFS(a+i,b+j,row,col);
			}
		}
	}
}

섬의 개수를 찾는 문제이다.

이 문제에서 핵심은 대각선에 있는 땅은 이어져있다고 판단하는 것이다.

처음에는 visited를 두고 풀었으나 다 풀고 난 후 다른 사람의 코드와 비교해 보니 굳이 visited가 필요 없었다.

방문해 준 땅을 0으로 바꿔주면 arr배열만 가지고 해결이 가능하다.

이와 비슷한 문제를 BFS를 통해 풀었었는데 이번에는 DFS로 문제를 풀어보았다.