생코에 이런 문제가 올라와있길래
간단히 풀릴 줄 알았는데 막상 풀어보려고 하니까
까다롭게 느껴지더라구요.
그래서 댓글을 보니
BFS 를 쓰라고 해서
나름 방법을 생각해봤는데 지적 부탁드림니다;
seom_soo 는 애교로 봐주십쇼
#include<stdio.h>
#define N 4
#define M 4
void bfs(int arr[N][M], int visited[N][M], int i, int j){
// array bound check
if(i < 0 || i >= N)
return;
if(j < 0 || j >= N)
return;
if (arr[i][j] == 0){ // if water, not interested
return;
}else if(visited[i][j] == 1){ // if already visited, not interested
return;
}else{
visited[i][j] = 1; // mark as visited
bfs(arr, visited, i+1, j); // up
bfs(arr, visited, i-1, j); // down
bfs(arr, visited, i, j+1); // right
bfs(arr, visited, i, j-1); // left
}
}
int find_seom_soo(int arr[N][M]){
int seom_soo = 0;
int visited[N][M] = {0,};
for(int i = 0; i < N; i++){
for(int j = 0; j < M; j++){
if (arr[i][j] == 0){
continue; // if water, proceed to the next element
}else if (visited[i][j] == 1){
continue; // if visited, proceed to the next
}else{
seom_soo++; // new island found
bfs(arr, visited, i, j); // explore
}
}
}
printf("seom soo : %d\n", seom_soo);
return seom_soo;
}
int main(){
int arr[N][M] = {{0, 1, 1, 1}, // 1 means land, 0 means water
{0, 0, 0, 0},
{1, 0, 0, 0},
{1, 1, 0, 0}};
find_seom_soo(arr);
int arr2[N][M] = {{1, 1, 0, 0},
{0, 0, 1, 0},
{1, 0, 1, 0},
{0, 1, 0, 1}};
find_seom_soo(arr2);
return 0;
}
그러니까
BFS 함수는 단순히
arr[i][j] 가 바다면 그냥 종료하고
배열 범위 안에서 벗어나면 그냥 종료하고
이미 예전에 같은 i, j 로 호출된적 있다면 그냥 종료하고
위 3가지 경우가 아니면
visited 를 1 로 설정한 다음
위, 아래, 좌, 우로 BFS를 재귀적으로 호출합니다.
이를 이용해서, 육지가 등장한다? 그러면 그 육지에 BFS 를 걸어버려서 위 아래 좌 우에 존재하는 모든 육지에 똑같이 visited = 1 으로 설정하게 합니다.
그 다음 main 함수로 돌아와서, for loop 로 배열을 차근차근 돌면서
arr[i][j] 가 바다라면 스킵하고
visited[i][j] 가 1 이라면 스킵하고
새로운 육지라면 seom_soo 를 1 올려두고 BFS 를 시전합니다.
대충 작동은 하는 것 같은데,
더 나은 방법이 있을까요?