문제

문제 링크

어떻게 접근할 것인가

  • 이 문제는 연결된 친구들의 개수를 구해주는 문제이다.
  • 따라서 BFS를 이용해서 또는 DFS를 이용해서 풀 수 있다.
  • BFS로 노드가 발견될 때까지 진행하고 발견된 노드는 0으로 바꿔주었다.

코드

#include <cstdio>
#include <vector>
#include <queue>
#define pii pair<int, int>
using namespace std;

int t, m, n, k, x, y; 
int d[4][2]= { {1, 0}, {-1, 0}, {0, 1}, {0, -1} };
int main(){
    scanf("%d", &t);
    while(t--){
        int cnt = 0;
        queue<pii> q;
        scanf("%d %d %d", &m, &n, &k);
        vector<vector<int> > v(m, vector<int>(n, 0));;
        while(k--){
            scanf("%d %d", &x, &y);
            v[x][y] = 1;
        }
        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                if(v[i][j] == 1){
                    q.push(pii(i, j));
                    v[i][j] = 0;
                    while(!q.empty()){
                        int fx = q.front().first, fy = q.front().second;
                        q.pop();
                        for(int k = 0; k < 4; k++){
                            int nx = fx + d[k][0], ny = fy + d[k][1];
                            if(nx >= m || nx < 0 || ny >= n || ny < 0 || !v[nx][ny])continue;
                            v[nx][ny] = 0;
                            q.push(pii(nx, ny));
                        }
                    }
                    cnt++;
                }
            }
        }
        printf("%d\n", cnt);
    }   
}

느낀점

  • BFS로 간단하게 끝내버린 문제이다.