[BFS] (백준 4963) 섬의 개수

알고리즘

BFS

 

 

[문제 본문]

문제

정사각형으로 이루어져 있는 섬과 바다 지도가 주어진다. 섬의 개수를 세는 프로그램을 작성하시오.

한 정사각형과 가로, 세로 또는 대각선으로 연결되어 있는 사각형은 걸어갈 수 있는 사각형이다. 

두 정사각형이 같은 섬에 있으려면, 한 정사각형에서 다른 정사각형으로 걸어서 갈 수 있는 경로가 있어야 한다. 지도는 바다로 둘러싸여 있으며, 지도 밖으로 나갈 수 없다.

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다.

둘째 줄부터 h개 줄에는 지도가 주어진다. 1은 땅, 0은 바다이다.

입력의 마지막 줄에는 0이 두 개 주어진다.

출력

각 테스트 케이스에 대해서, 섬의 개수를 출력한다.

제한

예제 입력 1

1 1
0
2 2
0 1
1 0
3 2
1 1 1
1 1 1
5 4
1 0 1 0 0
1 0 0 0 0
1 0 1 0 1
1 0 0 1 0
5 4
1 1 1 0 1
1 0 1 0 1
1 0 1 0 1
1 0 1 1 1
5 5
1 0 1 0 1
0 0 0 0 0
1 0 1 0 1
0 0 0 0 0
1 0 1 0 1
0 0

예제 출력 1

0
1
1
3
1
9

힌트

W3sicHJvYmxlbV9pZCI6IjQ5NjMiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWMxMmNcdWM3NTggXHVhYzFjXHVjMjE4IiwiZGVzY3JpcHRpb24iOiI8cD5cdWM4MTVcdWMwYWNcdWFjMDFcdWQ2MTVcdWM3M2NcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YjI5NCBcdWMxMmNcdWFjZmMgXHViYzE0XHViMmU0IFx1YzljMFx1YjNjNFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YzEyY1x1Yzc1OCBcdWFjMWNcdWMyMThcdWI5N2MgXHVjMTM4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuXHJcbjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvaXNsYW5kLnBuZ1wiIHN0eWxlPVwid2lkdGg6IDI4M3B4OyBoZWlnaHQ6IDE0MXB4O1wiIFwvPjxcL3A+XHJcblxyXG48cD5cdWQ1NWMgXHVjODE1XHVjMGFjXHVhYzAxXHVkNjE1XHVhY2ZjIFx1YWMwMFx1Yjg1YywgXHVjMTM4XHViODVjIFx1YjYxMFx1YjI5NCBcdWIzMDBcdWFjMDFcdWMxMjBcdWM3M2NcdWI4NWMgXHVjNWYwXHVhY2IwXHViNDE4XHVjNWI0IFx1Yzc4OFx1YjI5NCBcdWMwYWNcdWFjMDFcdWQ2MTVcdWM3NDAgXHVhYzc4XHVjNWI0XHVhYzA4IFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVjMGFjXHVhYzAxXHVkNjE1XHVjNzc0XHViMmU0LiZuYnNwOzxcL3A+XHJcblxyXG48cD5cdWI0NTAgXHVjODE1XHVjMGFjXHVhYzAxXHVkNjE1XHVjNzc0IFx1YWMxOVx1Yzc0MCBcdWMxMmNcdWM1ZDAgXHVjNzg4XHVjNzNjXHViODI0XHViYTc0LCBcdWQ1NWMgXHVjODE1XHVjMGFjXHVhYzAxXHVkNjE1XHVjNWQwXHVjMTFjIFx1YjJlNFx1Yjk3OCBcdWM4MTVcdWMwYWNcdWFjMDFcdWQ2MTVcdWM3M2NcdWI4NWMgXHVhYzc4XHVjNWI0XHVjMTFjIFx1YWMwOCBcdWMyMTggXHVjNzg4XHViMjk0IFx1YWNiZFx1Yjg1Y1x1YWMwMCBcdWM3ODhcdWM1YjRcdWM1N2MgXHVkNTVjXHViMmU0LiBcdWM5YzBcdWIzYzRcdWIyOTQgXHViYzE0XHViMmU0XHViODVjIFx1YjQ1OFx1YjdlY1x1YzJmOFx1YzVlYyBcdWM3ODhcdWM3M2NcdWJhNzAsIFx1YzljMFx1YjNjNCBcdWJjMTZcdWM3M2NcdWI4NWMgXHViMDk4XHVhYzA4IFx1YzIxOCBcdWM1YzZcdWIyZTQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWM3ODVcdWI4MjVcdWM3NDAgXHVjNWVjXHViN2VjIFx1YWMxY1x1Yzc1OCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWIyZTQuIFx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVjOWMwXHViM2M0XHVjNzU4IFx1YjEwOFx1YmU0NCB3XHVjNjQwIFx1YjE5Mlx1Yzc3NCBoXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gd1x1YzY0MCBoXHViMjk0IDUwXHViY2Y0XHViMmU0IFx1Yzc5MVx1YWM3MFx1YjA5OCBcdWFjMTlcdWM3NDAgXHVjNTkxXHVjNzU4IFx1YzgxNVx1YzIxOFx1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViNDU4XHVjOWY4IFx1YzkwNFx1YmQ4MFx1ZDEzMCBoXHVhYzFjIFx1YzkwNFx1YzVkMFx1YjI5NCBcdWM5YzBcdWIzYzRcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAxXHVjNzQwIFx1YjU0NSwgMFx1Yzc0MCBcdWJjMTRcdWIyZTRcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1Yzc4NVx1YjgyNVx1Yzc1OCBcdWI5YzhcdWM5YzBcdWI5YzkgXHVjOTA0XHVjNWQwXHViMjk0IDBcdWM3NzQgXHViNDUwIFx1YWMxYyBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM1ZDAgXHViMzAwXHVkNTc0XHVjMTFjLCBcdWMxMmNcdWM3NTggXHVhYzFjXHVjMjE4XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJLb3JlYW4ifSx7InByb2JsZW1faWQiOiI0OTYzIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiSG93IE1hbnkgSXNsYW5kcz8iLCJkZXNjcmlwdGlvbiI6IjxwPllvdSBhcmUgZ2l2ZW4gYSBtYXJpbmUgYXJlYSBtYXAgdGhhdCBpcyBhIG1lc2ggb2Ygc3F1YXJlcywgZWFjaCByZXByZXNlbnRpbmcgZWl0aGVyIGEgbGFuZCBvciBzZWEgYXJlYS4gRmlndXJlIEItMSBpcyBhbiBleGFtcGxlIG9mIGEgbWFwLjxcL3A+XHJcblxyXG48cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL2lzbGFuZC5wbmdcIiBzdHlsZT1cImhlaWdodDoxNDFweDsgd2lkdGg6MjgzcHhcIiBcLz48XC9wPlxyXG5cclxuPHA+RmlndXJlIEItMTogQSBtYXJpbmUgYXJlYSBtYXA8XC9wPlxyXG5cclxuPHA+WW91IGNhbiB3YWxrIGZyb20gYSBzcXVhcmUgbGFuZCBhcmVhIHRvIGFub3RoZXIgaWYgdGhleSBhcmUgaG9yaXpvbnRhbGx5LCB2ZXJ0aWNhbGx5LCBvciBkaWFnb25hbGx5IGFkamFjZW50IHRvIGVhY2ggb3RoZXIgb24gdGhlIG1hcC4gVHdvIGFyZWFzIGFyZSBvbiB0aGUgc2FtZSBpc2xhbmQgaWYgYW5kIG9ubHkgaWYgeW91IGNhbiB3YWxrIGZyb20gb25lIHRvIHRoZSBvdGhlciBwb3NzaWJseSB0aHJvdWdoIG90aGVyIGxhbmQgYXJlYXMuIFRoZSBtYXJpbmUgYXJlYSBvbiB0aGUgbWFwIGlzIHN1cnJvdW5kZWQgYnkgdGhlIHNlYSBhbmQgdGhlcmVmb3JlIHlvdSBjYW5ub3QgZ28gb3V0c2lkZSBvZiB0aGUgYXJlYSBvbiBmb290LjxcL3A+XHJcblxyXG48cD5Zb3UgYXJlIHJlcXVlc3RlZCB0byB3cml0ZSBhIHByb2dyYW0gdGhhdCByZWFkcyB0aGUgbWFwIGFuZCBjb3VudHMgdGhlIG51bWJlciBvZiBpc2xhbmRzIG9uIGl0LiBGb3IgaW5zdGFuY2UsIHRoZSBtYXAgaW4gRmlndXJlIEItMSBpbmNsdWRlcyB0aHJlZSBpc2xhbmRzLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGlucHV0IGNvbnNpc3RzIG9mIGEgc2VyaWVzIG9mIGRhdGFzZXRzLCBlYWNoIGJlaW5nIGluIHRoZSBmb2xsb3dpbmcgZm9ybWF0LjxcL3A+XHJcblxyXG48cD53IGg8YnIgXC8+XHJcbmMxLDEgYzEsMiAuLi4gYzEsdzxiciBcLz5cclxuYzIsMSBjMiwyIC4uLiBjMix3PGJyIFwvPlxyXG4uLi48YnIgXC8+XHJcbmNoLDEgY2gsMiAuLi4gY2gsdzxcL3A+XHJcblxyXG48cD53IGFuZCBoIGFyZSBwb3NpdGl2ZSBpbnRlZ2VycyBubyBtb3JlIHRoYW4gNTAgdGhhdCByZXByZXNlbnQgdGhlIHdpZHRoIGFuZCB0aGUgaGVpZ2h0IG9mIHRoZSBnaXZlbiBtYXAsIHJlc3BlY3RpdmVseS4gSW4gb3RoZXIgd29yZHMsIHRoZSBtYXAgY29uc2lzdHMgb2YgdyZ0aW1lcztoIHNxdWFyZXMgb2YgdGhlIHNhbWUgc2l6ZS4gdyBhbmQgaCBhcmUgc2VwYXJhdGVkIGJ5IGEgc2luZ2xlIHNwYWNlLjxcL3A+XHJcblxyXG48cD5jaSwgaiBpcyBlaXRoZXIgMCBvciAxIGFuZCBkZWxpbWl0ZWQgYnkgYSBzaW5nbGUgc3BhY2UuIElmIGNpLCBqID0gMCwgdGhlIHNxdWFyZSB0aGF0IGlzIHRoZSBpLXRoIGZyb20gdGhlIGxlZnQgYW5kIGotdGggZnJvbSB0aGUgdG9wIG9uIHRoZSBtYXAgcmVwcmVzZW50cyBhIHNlYSBhcmVhLiBPdGhlcndpc2UsIHRoYXQgaXMsIGlmIGNpLCBqID0gMSwgaXQgcmVwcmVzZW50cyBhIGxhbmQgYXJlYS48XC9wPlxyXG5cclxuPHA+VGhlIGVuZCBvZiB0aGUgaW5wdXQgaXMgaW5kaWNhdGVkIGJ5IGEgbGluZSBjb250YWluaW5nIHR3byB6ZXJvcyBzZXBhcmF0ZWQgYnkgYSBzaW5nbGUgc3BhY2U8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5Gb3IgZWFjaCBkYXRhc2V0LCBvdXRwdXQgdGhlIG51bWJlciBvZiB0aGUgaXNsYW5kcyBpbiBhIGxpbmUuIE5vIGV4dHJhIGNoYXJhY3RlcnMgc2hvdWxkIG9jY3VyIGluIHRoZSBvdXRwdXQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiRW5nbGlzaCJ9XQ==

 

[푼 코드]

#include <iostream>
#include <queue>
using namespace std;
struct Pos {
	int x;
	int y;
};
int N, M;
int arr[51][51];
int visit[51][51];
int dx[8] = { -1,0,1,-1,1,-1,0,1};
int dy[8] = { -1,-1,-1,0,0,1,1,1};

int result = 0;

bool IsRange(Pos p)
{
	return (p.x >= 0 && p.x < N&& p.y >= 0 && p.y < M);
}
void Solved(int x,int y)
{
	visit[y][x] = true;
	if (arr[y][x] == 0) return;
	queue<Pos> q;
	q.push({ x,y });
	result++;
	while (!q.empty())
	{
		Pos temp = q.front();
		q.pop();
		for (int i = 0; i < 8; i++)
		{
			Pos nPos;
			nPos.x = temp.x + dx[i];
			nPos.y = temp.y + dy[i];
			if (IsRange(nPos) && !visit[nPos.y][nPos.x] && arr[nPos.y][nPos.x] == 1)
			{
				q.push(nPos);
				visit[nPos.y][nPos.x] = true;
			}
		}
	}
}

int main()
{
	while (1)
	{
		cin >> N >> M;
		if (N == 0 && M == 0) break;
		result = 0;
		for (int y = 0; y < M; y++)
		{
			for (int x = 0; x < N; x++)
			{
				cin >> arr[y][x];
				visit[y][x] = false;
			}
		}

		for (int y = 0; y < M; y++)
		{
			for (int x = 0; x < N; x++)
			{
				if (!visit[y][x])
				{
					Solved(x, y);
				}
			}
		}
		cout << result << '\n';
	}
}

 

 

#BFS #알고리즘 #백준