[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는 그냥 인접 노드를 방문하고 방문 체크만 해주면 된다.
Author And Source
이 문제에 관하여([C++] 백준 1012 : 유기농 배추), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@lamknh/C-백준-1012-유기농-배추저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)