[문제 본문]
더보기
문제
정사각형으로 이루어져 있는 섬과 바다 지도가 주어진다. 섬의 개수를 세는 프로그램을 작성하시오.
한 정사각형과 가로, 세로 또는 대각선으로 연결되어 있는 사각형은 걸어갈 수 있는 사각형이다.
두 정사각형이 같은 섬에 있으려면, 한 정사각형에서 다른 정사각형으로 걸어서 갈 수 있는 경로가 있어야 한다. 지도는 바다로 둘러싸여 있으며, 지도 밖으로 나갈 수 없다.
출력
각 테스트 케이스에 대해서, 섬의 개수를 출력한다.
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 #알고리즘 #백준