boj 1012 c++ 유기농 배추

boj 1012 c++ 유기농 배추

백준 1012 cpp 유기농 배추

 

row, col 반대로 받아서 한번 고생하고, Q.pop() 을 엉뚱한 데 둬서 또 고생한 문제 ㅠㅠ

난이도 자체는 쉬움이다.

 

논리

1 - ea 를 받아서 ea 번 로직을 돌며 답을 출력한다.

1 .1 - 먼저 vis, board 를 모두 0으로 초기화한다.

1 .2 - 가로, 세로 순으로 들어오므로 col, row를 받는다.

1 .3 - posCount 라는 변수를 두고 cin 으로 받은 뒤, 그 변수 값 만큼 돌며 좌표 위치를 받아 board에 배추를 심는다.

1 .4 - int i = 0 -> row / int j = 0 -> col 을 돌면서 board의 (i, j) 번째 값이 1이면 Q에 넣는다.

1 .4 .1 Q 에 넣은 좌표를 vis 에서 true로 바꿔준다.

1 .4 .2 Q에 넣을 때마다 테스트케이스(posCount)의 ans를 1 증가시킨다.

1 .4 .2 .1 int k 가 0 ~ 4를 돌면서 현재 위치로부터 + (1, 0), +(0, 1), +(-1, 0), +(0, -1)에 각각 방문하도록 한다.

1 .4 .2 .2 범위를 벗어나는 경우(dx < 0, dy < 0, dx >= row, dy >= col) 그리고 이미 방문한 경우(vis[dx][dy] == true) 그리고 배추가 심어져 있지 않은 곳을 방문한 경우(board[dx][dy] == 0) 는 제외하고

1 .4 .2 .3 Q에 dx, dy 좌표를 넣는다.

1 .4 .2 .4 dx, dy 도 방문했다는 표시를 남긴다.

1 .5 - ans 를 출력한다.

2 - 1을 반복한다.

 

#include <bits/stdc++.h>
using namespace std;

int ea;
bool vis[52][52];
int board[52][52];
int row, col;
queue <pair<int, int>> Q;
int dirX[4] = {0, 1, 0, -1};
int dirY[4] = {-1, 0, 1, 0};

# define X first
# define Y second

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> ea;
    while (ea--) //ea번 반복.
    {
        // 아래 for문은 board, vis를 전부 0으로 초기화.
        for (int b = 0; b < 51; b++)
            fill(board[b], board[b] + 51, 0);
        for (int b = 0; b < 51; b++)
            fill(vis[b], vis[b] + 51, false);
        int posCount;
        cin >> row >> col >> posCount;
        while (posCount--) //pCount번 반복
        { // board 에서 배추 위치를 1로 변경.
            int posX;
            int posY;
            cin >> posX >> posY;
            board[posX][posY] = 1;
        }
        int ans = 0;
        for (int i = 0; i < row; i++)
        {
            for (int j = 0; j < col; j++)
            {
                if (board[i][j] == 1 && vis[i][j] == false)
                {
                    Q.push({i, j});
                    vis[i][j] = true;
                    ans++;
                    while (!Q.empty())
                    {
                        auto cur = Q.front();
                        Q.pop();
                        for (int k = 0; k < 4; k++)
                        {
                            int dx = cur.X + dirX[k];
                            int dy = cur.Y + dirY[k];
                            if (dx < 0 || dy < 0 || dx >= row || dy >= col)
                                continue;
                            if (vis[dx][dy] == true || board[dx][dy] == 0)
                                continue;
                            Q.push({dx, dy});
                            vis[dx][dy] = true;
                        }
                    }
                }
            }
        }
        cout << ans << '\n';
    }
}