BOJ : 1012 유기농 배추 (C++)

14521 단어 bojboj

문제

Code

#include <iostream>
#include <queue>
#include <utility>

using namespace std;
#define X first
#define Y second
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    int T;
    cin >> T;

    while(T--)
    {
        int M, N, K, num=0;
        int board[52][52];
        int vis[52][52];
        /* 입력 시작 */
        cin >> M >> N >> K;  // M : x / N : y
        for(int i=0;i < M;i++)
        {
            fill(board[i],board[i]+M,0);
            fill(vis[i],vis[i]+M,0);
        }
        for(int i=0;i<K;i++)
        {
            pair<int,int> tmp;
            cin >> tmp.X >> tmp.Y;
            board[tmp.X][tmp.Y] = 1;
        }

        for(int i=0;i<M;i++)
        {
            for(int j=0;j<N;j++)
            {
                if(vis[i][j] || board[i][j] != 1) continue;
                num++;
                queue<pair<int,int>> Q;
                Q.push({i,j});
                vis[i][j] = 1;
                while(!Q.empty())
                {
                    auto cur = Q.front(); Q.pop();
                    for(int dir=0;dir<4;dir++)
                    {
                        int nx = cur.X + dx[dir];
                        int ny = cur.Y + dy[dir];
                        if(nx < 0 || nx >= M || ny<0 || ny>= N) continue;
                        if(vis[nx][ny] || board[nx][ny] != 1) continue;
                        vis[nx][ny] = 1;
                        Q.push({nx, ny});
                    }
                }
            }
        }
        cout << num <<'\n';
    }
}
  • 난이도는 쉬움
  • 문제에서 배추밭의 가로길이 = M
                                 세로길이 = N 이라고 해서
    N*M배열로 접근했는데 반대였다.
    (?왜지? 알면 알려줘여)

좋은 웹페이지 즐겨찾기