[C++]白準1012:有機白菜
#include <iostream>
int map[51][51] = {0}; // 배추 있으면 1
bool visited[51][51] = {false}; // 방문 여부
// 상하좌우 탐색
int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};
int T; // 테스트 케이스 개수
int M, N, K; // 가로, 세로, 배추 위치 개수
int X, Y; // 배추 위치
void DFS(int x, int y){
visited[x][y] = true; // 방문처리
//상하좌우 다 찾아야하면 반복문 사용
for(int i = 0; i < 4; i++){
int nx = x + dx[i];
int ny = y + dy[i];
if(map[nx][ny] == 1 && !visited[nx][ny]){ // 연결된 것이 있고 탐색된 적 없는 경우
DFS(nx, ny); // 탐색
}
}
}
int main(int argc, char** argv){
scanf("%d", &T);
for(int i = 0; i < T; i++){
int cnt = 0;
scanf("%d %d %d", &M, &N, &K);
for(int j = 0; j < K; j++){
scanf("%d %d", &X, &Y);
map[X][Y] = 1; // 배추 있으면 1
}
for(int j = 0; j <= 50; j++){
for(int k = 0; k <= 50; k++){
if(map[j][k] == 1 && !visited[j][k]){
DFS(j, k);
cnt++;
}
}
}
printf("%d\n", cnt);
//초기화
cnt = 0;
for(int j = 0; j <= 50; j++){
for(int k = 0; k <= 50; k++){
map[j][k] = 0;
visited[j][k] = false; // 방문도 초기화 시켜주기
}
}
}
return 0;
}
上下左右をブラウズするには、dx、dy、for文を使用してブラウズする必要があります.
DFSはアクセスチェックが必要です.初期化する場合は、アクセスチェックも一緒に初期化します.
cntの場合、隣接アクセスが終了した後にcntを追加すればよいので、DFSは隣接ノードにアクセスしてアクセスチェックを行うだけでよい.
Reference
この問題について([C++]白準1012:有機白菜), 我々は、より多くの情報をここで見つけました https://velog.io/@lamknh/C-백준-1012-유기농-배추テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol