๋ณธ๋ฌธ ๋ฐ”๋กœ๊ฐ€๊ธฐ

๐Ÿ“ ์•Œ๊ณ ๋ฆฌ์ฆ˜/Code Tree

[์ฝ”๋“œํŠธ๋ฆฌ] BFS ํƒ์ƒ‰ / ๊ฐˆ ์ˆ˜ ์žˆ๋Š” ๊ณณ๋“ค

728x90

๊ฐˆ ์ˆ˜ ์žˆ๋Š” ๊ณณ๋“ค

์ˆซ์ž 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;
}

 

ํ•ด์„ค ์•ˆ๋ณด๊ณ  ํ’€์–ด๋ƒˆ๋”ฐ

 

728x90