BOJ #1012

문제

탐색 유형 문제로 dfs, bfs 알고리즘으로 풀이가 가능하다.
bfs 알고리즘를 이용하였고, 한 열의 탐색이 끝나면
다음 열로 옮기는 식으로 구현해보았다.
탐색 기준점은 큐의 front로, 기준점을 정하면
front값을 pop을 해주고 기준점에서 상하좌우 탐색이 끝나면
다음 기준점으로 넘어가는 방식이다.

테스트케이스가 존재해, t가 2 이상이면 배열을
초기화해주어야해서 fill을 통해 구현하였다.

코드

#include <iostream>
#include <algorithm>
#include <vector>
#pragma warning(disable:4996)
#include <sstream>
#include <math.h>
#define endl '\n'
#include <queue>

using namespace std;
typedef long long ll;

#define X first
#define Y second

int board[51][51];
bool visited[51][51];
int dx[] = {1,0,-1,0};
int dy[] = {0,1,0,-1};
int m,n,k;
queue<pair<int, int>> q;

void bfs(int x, int y){
    visited[x][y] = 1;
    q.push(make_pair(x, y));
    while(!q.empty()){
        auto cur = q.front(); q.pop();
        for(int i=0; i<4; i++){
            int nx = cur.X + dx[i];
            int ny = cur.Y + dy[i];
            if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
            if(visited[nx][ny] == 1 || board[nx][ny] != 1) continue;
            
            visited[nx][ny] = 1;
            q.push(make_pair(nx,ny));
        }
    }
}

int main(int argc, const char * argv[]){
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(nullptr);
    
    int t;
    cin >> t;
    
    while(t--){
        cin >> m >> n >> k;
        
        int x,y;
        // 심어져 있는 곳 체크
        for(int i=0; i<k; i++){
            cin >> x >> y;
            board[y][x] = 1;
        }
        int count=0; // 지렁이 수
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if(board[i][j]==1 && visited[i][j] != 1){
                    bfs(i, j);
                    count++;
                }
            }
        }
        cout << count << endl;
//        int board[51][51] = {0, };
//        bool visited[51][51] = {0, };
        for(int i=0; i<n; i++){
            fill(board[i], board[i]+m, 0);
            fill(visited[i], visited[i]+m, 0);
        }
    }
    return 0;
}