[백준/c++] 1012 - 유기농 배추

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

1012번: 유기농 배추

---

1) 풀이

요거는 이전에 풀었던 '그림'문제와 똑같은 풀이 방식!

풀이 자체는 아래 글을 참고하면 될 것 같다.

2021.05.31 - [알고리즘 | 자료구조/백준] - [백준/c++] 1926 - 그림

[백준/c++] 1926 - 그림

 

여기까지 쓰고 넘어갈려다가 이 문제에서 많은 사람들이, 그리고 내가 놓치고 지나갔던 점들을 적어두려고 한다.

1. 문제에서 주어지는 가로, 세로, x, y 좌표를 잘 살펴보자! (열, 행)

2. 여러 테스트 케이스를 풀어야 하는 문제이므로, 배열이나 큐, 변수 초기화에 유의하자!

 

요 두개만 유의해서 풀어도 쉽게 풀리는 문제이당!

알바하고 오니까 너무너무 피곤해서 이만 줄이겠다

 

2) 최종 소스코드

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
#include <algorithm>
using namespace std;
int board[52][52]; //배추밭
bool visited[52][52]; //해당 칸을 방문했는지 체크
int cx[4] = {0,1,0,-1}; //상하좌우 탐색 x좌표
int cy[4] = {1,0,-1,0}; //상하좌우 탐색 y좌표
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	int t;
	cin >> t; //테스트케이스 개수
	while(t--) {
		memset(board, 0, sizeof(board)); //초기화
		memset(visited, false, sizeof(visited));
		int m, n, k;
		cin >> m >>  n >> k;
		for (int j = 0; j < k; j++) {
			int x, y;
			cin >> y >> x;
			board[x][y] = 1;
		}
		

		queue<pair<int, int>>q;
		int cnt = 0;
		for (int j = 0; j < n; j++) {
			for (int h = 0; h < m; h++) {
				if (board[j][h] != 1||visited[j][h]==true) continue;
					q.push({ j,h });
					visited[j][h] = true;

					while (!q.empty()){
						pair<int, int>cur = q.front();
						q.pop();

						for (int k = 0; k < 4; k++) {
							int dx = cur.first + cx[k];
							int dy = cur.second + cy[k];
							if (dx < 0 || dx >= n || dy < 0 || dy >= m) continue;
							if (visited[dx][dy] == true || board[dx][dy] != 1) continue;

							q.push({ dx,dy });
							visited[dx][dy] = true;
						}
					}
					cnt++; //반복문을 빠져나오면, 더이상 인접하는 배추가 없다는 뜻
				}

		}
		cout <<cnt << '\n';
		
			
	}

}

3) 참고자료