๊ฐ ์ ์๋ ๊ณณ๋ค
์ซ์ 0, 1๋ก๋ง ์ด๋ฃจ์ด์ง n * n ๊ฒฉ์๊ฐ ์ฃผ์ด์ก์ ๋, k๊ฐ์ ์์์ ์ผ๋ก๋ถํฐ ์ํ์ข์ฐ ์ธ์ ํ ๊ณณ์ผ๋ก๋ง ์ด๋ํ์ฌ ๋๋ฌ ๊ฐ๋ฅํ ์นธ์ ์๋ฅผ ๊ตฌํ๋ ํ๋ก๊ทธ๋จ์ ์์ฑํด๋ณด์ธ์. ์ซ์ 0์ ํด๋น ์นธ์ด ์ด๋ํ ์ ์๋ ๊ณณ์์, ์ซ์ 1์ ํด๋น ์นธ์ด ์ด๋ํ ์ ์๋ ๊ณณ์์ ์๋ฏธํฉ๋๋ค.
์ ๋ ฅ ํ์
์ฒซ ๋ฒ์งธ ์ค์๋ ๊ฒฉ์์ ํฌ๊ธฐ๋ฅผ ๋ํ๋ด๋ n๊ณผ ์์์ ์ ์๋ฅผ ๋ํ๋ด๋ k ๊ฐ์ด ๊ณต๋ฐฑ์ ์ฌ์ด์ ๋๊ณ ์ฃผ์ด์ง๋๋ค.
๋ ๋ฒ์งธ ์ค ๋ถํฐ๋ n๊ฐ์ ์ค์ ๊ฑธ์ณ ๊ฐ ํ์ ํด๋นํ๋ n๊ฐ์ ์ซ์๊ฐ ์์๋๋ก ๊ณต๋ฐฑ์ ์ฌ์ด์ ๋๊ณ ์ฃผ์ด์ง๋๋ค.
๊ทธ ๋ค์ ์ค ๋ถํฐ๋ k๊ฐ์ ์ค์ ๊ฑธ์ณ ๊ฐ ์์์ ์ ์์น (r, c)๊ฐ ๊ณต๋ฐฑ์ ์ฌ์ด์ ๋๊ณ ์ฃผ์ด์ง๋๋ค. (r, c)๋ rํ c์ด ์์น๊ฐ ์์์ ์ค ํ๋์์ ์๋ฏธํฉ๋๋ค. ๋ชจ๋ ์์์ ์ ์์น์ ์ ํ์๋ ์ซ์๋ 0์ด๊ณ , ์์์ ๋ผ๋ฆฌ ์๋ก ๊ฒน์น์ง ์๊ฒ ์ฃผ์ด์ง๋ค๊ณ ๊ฐ์ ํด๋ ์ข์ต๋๋ค. (1 ≤ r ≤ n, 1 ≤ c ≤ n)
- 1 ≤ n ≤ 100
- 1 ≤ k ≤ n * n
์ถ๋ ฅ ํ์
์์์ง์ ์ผ๋ก๋ถํฐ ๋ฐฉ๋ฌธ์ด ๊ฐ๋ฅํ ์๋ก ๋ค๋ฅธ ์นธ์ ์๋ฅผ ์ถ๋ ฅํฉ๋๋ค.
๋์ ํ์ด
#include <iostream>
#include <queue>
using namespace std;
int n; int k;
int mat[101][101]={0,};
int visited[101][101] = {0,};
int cnt=0;
bool CanGo(int r, int c){
if(r>n || c>n || r<1 || c<1) return false;
if(visited[r][c]==1) return false;
if(mat[r][c]==1) return false;
return true;
}
int bfs(int r, int c){
int dx[4] = {1,0,-1,0};
int dy[4] = {0,1,0,-1};
queue<pair<int,int> > q;
q.push(make_pair(r,c));
if(visited[r][c]==0) cnt++;
visited[r][c]=1;
while(!q.empty()){
pair<int,int> a = q.front(); // ์ฌ๊ธฐ์ ํ์ ์ฒซ pair๋ฅผ ์ ์ฅํด๋๊ณ
q.pop();
for(int i=0; i<4; ++i){
int nr = a.first +dx[i]; // ์ฒซ pair์๋ ๊ฐ์์ ์ด๋์์ผ์ผํจ.!!
int nc = a.second +dy[i];
if(CanGo(nr, nc)){
q.push(make_pair(nr,nc));
visited[nr][nc] = 1;
cnt++;
}
}
}
}
int main() {
cin >> n>>k;
for(int i=1; i<=n; ++i){
for(int j=1; j<=n; ++j) cin>>mat[i][j];
}
int r; int c;
for(int i=0; i<k; ++i){
cin>>r>>c;
bfs(r, c);
}
cout << cnt;
return 0;
}
ํด์ค ์๋ณด๊ณ ํ์ด๋๋ฐ