https://www.acmicpc.net/problem/4963
๋ฌธ์
์ ์ฌ๊ฐํ์ผ๋ก ์ด๋ฃจ์ด์ ธ ์๋ ์ฌ๊ณผ ๋ฐ๋ค ์ง๋๊ฐ ์ฃผ์ด์ง๋ค. ์ฌ์ ๊ฐ์๋ฅผ ์ธ๋ ํ๋ก๊ทธ๋จ์ ์์ฑํ์์ค.
ํ ์ ์ฌ๊ฐํ๊ณผ ๊ฐ๋ก, ์ธ๋ก ๋๋ ๋๊ฐ์ ์ผ๋ก ์ฐ๊ฒฐ๋์ด ์๋ ์ฌ๊ฐํ์ ๊ฑธ์ด๊ฐ ์ ์๋ ์ฌ๊ฐํ์ด๋ค.
๋ ์ ์ฌ๊ฐํ์ด ๊ฐ์ ์ฌ์ ์์ผ๋ ค๋ฉด, ํ ์ ์ฌ๊ฐํ์์ ๋ค๋ฅธ ์ ์ฌ๊ฐํ์ผ๋ก ๊ฑธ์ด์ ๊ฐ ์ ์๋ ๊ฒฝ๋ก๊ฐ ์์ด์ผ ํ๋ค. ์ง๋๋ ๋ฐ๋ค๋ก ๋๋ฌ์ธ์ฌ ์์ผ๋ฉฐ, ์ง๋ ๋ฐ์ผ๋ก ๋๊ฐ ์ ์๋ค.
์ ๋ ฅ
์ ๋ ฅ์ ์ฌ๋ฌ ๊ฐ์ ํ ์คํธ ์ผ์ด์ค๋ก ์ด๋ฃจ์ด์ ธ ์๋ค. ๊ฐ ํ ์คํธ ์ผ์ด์ค์ ์ฒซ์งธ ์ค์๋ ์ง๋์ ๋๋น w์ ๋์ด h๊ฐ ์ฃผ์ด์ง๋ค. w์ h๋ 50๋ณด๋ค ์๊ฑฐ๋ ๊ฐ์ ์์ ์ ์์ด๋ค.
๋์งธ ์ค๋ถํฐ h๊ฐ ์ค์๋ ์ง๋๊ฐ ์ฃผ์ด์ง๋ค. 1์ ๋ , 0์ ๋ฐ๋ค์ด๋ค.
์ ๋ ฅ์ ๋ง์ง๋ง ์ค์๋ 0์ด ๋ ๊ฐ ์ฃผ์ด์ง๋ค.
์ถ๋ ฅ
๊ฐ ํ ์คํธ ์ผ์ด์ค์ ๋ํด์, ์ฌ์ ๊ฐ์๋ฅผ ์ถ๋ ฅํ๋ค.
ํ์ด
dfs ๋ฌธ์ ๋ผ์ ํ์ด๋ฒ๋ง ์๋ฉด ๊ธ๋ฐฉ ํ ์ ์๋ค
ํ์๋ ๋ฒกํฐ๋ฅผ ํ๋๋ง ์ฌ์ฉํ๊ณ ์ถ์ด์ ์ ๋ ฅ๋ฐ์ ์ง๋ ๋ฒกํฐ์ ๋ฐ๋ก ์ฌ์ ํ์ํ๋ค.
๋ ์ด 1๋ก ๋์ด์์ผ๋ฏ๋ก 2๋ถํฐ ์นด์ดํ ํ๊ณ ๋ฆฌํดํ ๋ 1์ ๋นผ์ฃผ์๋ค
// ํ์ด : https://whkakrkr.tistory.com
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
typedef pair<int,int> ci;
int dx[8] = {0,0,-1,1,1,-1,1,-1};
int dy[8] = {1,-1,0,0,-1,1,1,-1};
int w,h;
int solution(vector<vector<int>>&v) {
int cnt = 1;
for(int i=0; i<h; i++) {
for(int j=0; j<w; j++) {
if(v[i][j]!=1) continue;
cnt++;
queue<ci> q;
q.push({i,j});
while(!q.empty()) {
ci cur = q.front();
q.pop();
for(int dir=0; dir<8; dir++) {
int x = cur.first + dir[dx];
int y = cur.second + dir[dy];
if(x<0 || x>=h || y<0 || y>=w) continue;
if(v[x][y]!=1) continue;
v[x][y] = cnt;
q.push({x,y});
}
}
}
}
return cnt-1;
}
int main() {
cin >> w >> h;
while(!(w==0 && h==0)) {
vector<vector<int>> v(h, vector<int>(w));
for(int i=0; i<h; i++) {
for(int j=0; j<w; j++) {
cin >> v[i][j];
}
}
cout << solution(v) << "\n";
cin >> w >> h;
}
}