[백준 C++] 1012번 유기농 배추

백준 C++ (cpp) 알고리즘 1012번 유기농 배추

1012번 유기농 배추 문제 링크

https://www.acmicpc.net/problem/1012

1012번: 유기농 배추

 

내 코드

주석 부분이 설명 및 디버깅 부분

#include <iostream>
#include <queue>

using namespace std;

/* X-1 X X+1 */
/*M-1 M M+1 */

#define Y first
#define X second

int dy[4] = { 1,0,-1,0 };
int dx[4] = { 0,1,0,-1 };

/* Test case 개수도 추가해주기*/
/* 가로는 M 세로는 N의 길이를 가져*/

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

	int T;
	cin >> T;

	for (int p = 0; p < T; p++) {
		int board[52][52] = { 0, };
		bool vis[52][52]{ 0, };
		int M, N, K;

		cin >> M >> N >> K;

		/* 값 넣기*/
		for (int i = 0; i < K; i++) {
			int X, Y;
			cin >> X >> Y;

			board[Y][X] = 1;
		}

		/*
		::cout << "I will print board\n";
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				::cout << board[i][j];

			}
			::cout << '\n';
		}*/

		int num = 0;
		/* for문 내부에서 시작점 찾기와 BFS를 돌리면 만사 해결 */
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) { /* 배추가 없거나 들린 부분이면 BFS 시작 못해*/
				if (board[i][j] == 0 || vis[i][j]) continue;
				num++;
				queue<pair<int, int>> Q;
				vis[i][j] = 1;
				Q.push({ i, j });
				//::cout << "=================\n";
				//::cout << "Start BFS " << i << " and " << j << '\n';
				while (!Q.empty()) {
					pair<int, int> 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[ny][nx] == 1 || board[ny][nx] == 0) continue;
						vis[ny][nx] = 1;
						Q.push({ ny,nx });
						//::cout << "I push " << ny << "and" << nx << '\n';
					}
				}

			}

		}


		cout << num<<'\n';
	}

}