배추 1개에 배추흰지렁이가 1마리라도 살고 있으면 지렁이는 인접한 배추로 이동이 가능하다. 인접한 배추도 해충 보호가 가능하다. 인접한 배추는 상하좌우에 위치한 경우이다.
배추흰지렁이의 총 개수를 구하여라
대공사입니다.
#include <iostream>
#include <queue>
using namespace std;
#define X first // pair에서 first, second를 줄여서 쓰기 위해서 사용
#define Y second // first -> X, second- > Y
// 테스트 케이스의 개수 T
// 배추밭의 가로길이 M
// 배추밭의 세로길이 N
// 배추가 심어져있는 위치의 개수 K
// 배추의 위치 X(0 ≤ X ≤ M-1), Y(0 ≤ Y ≤ N-1)
/*
int board[50][50] = {0,};
bool visited[50][50];
*/
int T, M, N, K;
int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,1,0,-1 };
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> T; // 테스트 케이스 입력 후
for (int i = 0; i < T; i++) { // T만큼 반복
int board[50][50] = { 0, };
bool visited[50][50];
cin >> M >> N >> K; // 가로 세로 배추 개수
queue<pair<int, int> > Q; // 큐를 좌표형태로 하기 위해 pair사용
int X, Y;
for (int j = 0; j < K; j++) {
cin >> X >> Y;
board[X][Y] = 1;
}
/*
//배열에 입력 값 모두 확인
for (int i = 0; i < N; i++) { // 한 행씩 받는다.
for (int j = 0; j < M; j++) {
cout << board[i][j] << " ";
}
cout << endl;
}
*/
int count = 0; // 총 필요한 지렁이의 수
for (int i = 0; i < N; i++) { // 가로 행 하나씩 받는다.
for (int j = 0; j < M; j++) {
if (board[i][j] == 0 || visited[i][j] == true) { // 배추가 없는 부분 or 이미 방문한 경우
continue;
}
// 처음 방문하는 배추일 경우
visited[i][j] = 1; //(i,j)를 방문했다고 표시
Q.push({ i,j }); //큐에 (i,j) 삽입
count++;
while (!Q.empty()) { // 큐의 내부가 빌 때까지 탐색
// 현재 지점을 저장하고 상하좌우 값을 더하는 이터레이터? 추가
pair<int, int> cur = Q.front(); // 이전에 넣은 큐의 front값을 변수에 저장
Q.pop(); // 큐의 front값을 pop
// 주변 상하좌우 배추 유무 탐색한다.
for (int dir = 0; dir < 4; dir++) {
// 순서대로 하(1,0) 우(0,1) 상(-1,0) 좌(0,-1)
// x-1,y
// x,y-1 x,y x,y+1
// x+1,y
int nx = cur.X + dx[dir];
int ny = cur.Y + dy[dir];
if (nx < 0 || nx >= N || ny < 0 || ny >= M) { // 범위 밖으로 벗어가는 경우
continue;
}
if (visited[nx][ny] == true || board[nx][ny] == 0) { // 이미 방문 or 방문하지 못함 경우
continue;
}
visited[nx][ny] = 1; // (nx,ny)를 방문했다고 표시
Q.push({ nx,ny }); // 큐에 (nx,ny)삽입
}
}
}
}
cout << count << endl;
}
}밖으로 빼는 버릇을 들이자
#include <iostream>
#include <queue>
using namespace std;
#define X first // pair에서 first, second를 줄여서 쓰기 위해서 사용
#define Y second // first -> X, second- > Y
// 테스트 케이스의 개수 T
// 배추밭의 가로길이 M
// 배추밭의 세로길이 N
// 배추가 심어져있는 위치의 개수 K
// 배추의 위치 X(0 ≤ X ≤ M-1), Y(0 ≤ Y ≤ N-1)
int board[50][50] = {0,};
bool visited[50][50];
int T, M, N, K;
int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,1,0,-1 };
Hello