[c++/알고리즘] 백준 1012 유기농배추 : dfs
문제 풀이
출발점이 따로 존재하지 않아서 BFS보다 DFS가 더 적합하다고 생각하여 DFS로 접근하였다.-> 다른 블로그보니 BFS로 푼 경우가 꽤 된다.- 한칸에 지렁이가 살고 있으면 왼/오/위/아래로 인접한 다른 배추로 이동할 수 있어 지렁이가 필요없다.
- 배추의 위치는 x : 0<=x<M ,y : 0<=y<N 이 주어진다.
- 배추가 인접해 있는 곳을 한개씩 카운트한다.
나의 코드
#include <iostream>
#include <cstring>
using namespace std;
int chk[51][51];
int map[51][51];
int dx[4] = {0, 1, 0 ,-1};
int dy[4] = {1, 0, -1, 0};
void DFS(int x, int y){
for(int i=0; i<4; i++) {
if (chk[x+dx[i]][y+dy[i]] == 0 && map[x+dx[i]][y+dy[i]] == 1) {
chk[x+dx[i]][y+dy[i]] = 1;
DFS(x+dx[i], y+dy[i]);
}
}
}
int main(){
int t, m, n, k, a, b, cnt = 0;
cin >> t;
for(int i=0; i<t; i++){
cin >> m >> n >> k;
// 배추의 갯수만큼 해당 x,y좌표에 배추 입력받기
for(int j=0; j<k; j++){
cin >> a >> b;
map[a][b] = 1;
}
if(k == 1){
cout << 1 << endl;
continue;
}
// 아직 방문하지 않았고, 배추가 심어져 있는곳에서 DFS 시작
// DFS가 종료되면 ( 한 지점에서 인접한 지점을 모두 방문했을때)
// cnt(배추지렁이의 수)를 1씩 증가시킨다.
for(int x=0; x<n; x++){
for(int y=0; y<m; y++){
if(chk[y][x] == 0 && map[y][x] == 1){
chk[y][x] = 1;
DFS(y, x);
cnt++;
}
}
}
cout << cnt << endl;
cnt = 0;
memset(chk, 0, sizeof(chk));
memset(map, 0, sizeof(map));
}
return 0;
}
Author And Source
이 문제에 관하여([c++/알고리즘] 백준 1012 유기농배추 : dfs), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@myeongs07/c알고리즘-백준-1012-유기농배추-dfs저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)