풀이방법: dfs
문제 해석
알고보니 예전에 틀렸던 문제이다, 왜 틀렸을까..
어렵지는 않다.
상하좌우 움직임 / dfs 만 알면된다.
풀이방식
한번 생각해보자 ,
지렁이는 움직인다. 지렁이가 이동하면서 모든 배추를 보호한다.
=> 다시말해서, 1이 모여있는 구역당 지렁이가 한마리면 된다.
상하좌우로 움직인다.
=> x,y가 움직일 두 개의 이동배열을 만든다.
int nx = x + dx[i];
int ny = y + dy[i];
1일때 dfs탐색을 시작한다.
=> map{i}{j}==1이면 탐색을 시작한다. 탐색을 시작할때마다 카운팅한다.
for (int i = 0; i < M ; i++) {
for (int j = 0; j < N ; j++) {
visitedi = true;
dfs(i, j);
cnt++;
}
}
}
방문했던것은 방문하지 않는다. (안하면 스택오버플로우)
=> 각 칸당 boolean 타입의 visited배열을 만들어 방문하면 true바꿔준다.
if (isRange(nx, ny)&& !visitednx&&mapnx==1) {
visitednx = true;
dfs(nx,ny);
}
이게 전부다. 그리고 재귀해주자,
코드 전체 보기
: 예전엔 왜 틀렸을까.. 중간에 10분정도 오류를 못찾았다.. 이유는..예제를 카운팅하면서 6으로 숫자를 세가지고
왜 5가 안되는거지 하면서 고민했다. 맞다 바보다..