생코펌) 2D 배열에서 섬의 갯수 찾는 알고리즘 질문


(ㄴㅂㄷㄱㄷㄱ) #1

생코에 이런 문제가 올라와있길래

간단히 풀릴 줄 알았는데 막상 풀어보려고 하니까
까다롭게 느껴지더라구요.

그래서 댓글을 보니
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 를 시전합니다.

대충 작동은 하는 것 같은데,

더 나은 방법이 있을까요?


(codesafer) #2

좌상단 모서리부터 우하단 모서리까지 회색을 흰색으로 칠하면서 칠한 횟수를 세는 flood fill


(ㄴㅂㄷㄱㄷㄱ) #3

!!!
감사함니다 ㅠㅜ


(ㄴㅂㄷㄱㄷㄱ) #4

아… 내 코드가 너무 부끄럽다


(바보털) #5

4방향입니까, 아님 8방향입니까?


(ㄴㅂㄷㄱㄷㄱ) #6

4방향인거 같죠 아무래도? 저도 퍼온거라…


(Vertex) #7

https://www.acmicpc.net/problem/4963

백준에 8방향으로 비슷한 문제가 있네요.


(바보털) #9

i0보다 작다, 즉 i-1이라는건 예전에 0 - 1을 했다는 건데, iunsigned로 잡아주면 42억이 되면서 자동으로 N보다 크겠지요?

비트연산 경계점검 찾아보세용~


(바보털) #10
#include <iostream>
#include <vector>

#define SIZE 1024

using pii  = std::pair  < int, int >;
using vpii = std::vector< pii >;

int  serosize, garosize;
char data[ SIZE ][ SIZE ] = { 0, },                         //1은 섬,  0은 물
     ch  [ SIZE ][ SIZE ] = { 0, };                         //1은 간곳, 0은 안간곳

void find_seom_soo(int sero, int garo)
{
      vpii st = { std::make_pair(sero, garo) };
      int  t1, t2;

      ch[ sero ][ garo ] = 1;

      for(; !st.empty(); )
      {
            t1 = st.back().first;
            t2 = st.back().second;
            st.pop_back();

            if(t2 > 0 && (data[ t1 ][ t2 - 1 ] ^ ch[ t1 ][ t2 - 1 ]))
            {
                  ch[ t1 ][ t2 - 1 ] = 1;
                  st.push_back(std::make_pair(t1, t2 - 1));
            }

            if(t2 + 1 < garosize && (data[ t1 ][ t2 + 1 ] ^ ch[ t1 ][ t2 + 1 ]))
            {
                  ch[ t1 ][ t2 + 1 ] = 1;
                  st.push_back(std::make_pair(t1, t2 + 1));
            }

            if(t1 > 0 && (data[ t1 - 1 ][ t2 ] ^ ch[ t1 - 1 ][ t2 ]))
            {
                  ch[ t1 - 1 ][ t2 ] = 1;
                  st.push_back(std::make_pair(t1 - 1, t2));
            }

            if(t1 + 1 < serosize && (data[ t1 + 1 ][ t2 ] ^ ch[ t1 + 1 ][ t2 ]))
            {
                  ch[ t1 + 1 ][ t2 ] = 1;
                  st.push_back(std::make_pair(t1 + 1, t2));
            }
      }
}

int main()
{
      int ans = 0;

      std::cin. sync_with_stdio(false);
      std::cout.sync_with_stdio(false);

      std::cin >> serosize >> garosize;

      for(int i = 0; i < serosize; ++i)
      {
            for(int j = 0; j < garosize; ++j)
            {
                  std::cin >> data[ i ][ j ];
                  data[ i ][ j ] -= '0';
            }
      }

      for(int i = 0; i < serosize; ++i)
      {
            for(int j = 0; j < garosize; ++j)
            {
                  if(data[ i ][ j ] ^ ch[ i ][ j ])
                  {
                        find_seom_soo(i, j);
                        ++ans;
                  }
            }
      }

      std::cout << ans << '\n';

      return 0;
}

아마 똑바로 돌아갈겁니다.


(ㄴㅂㄷㄱㄷㄱ) #11

윽… 그렇군요 ㄱㅅㄱㅅ
중간에 멋좀 부려본다고
int i -> size_t i 로 바꿨는데
저걸 신경 못썻네요…
감사함니다


(바보털) #12

visitedarr도 어차피 0 아니면 1인데 굳이 ==를 쓸 필요는…

이건 작은 팁입니당~

data가 0이고 ch가 0 → 바다
data가 0이고 ch가 1 → 그런거 없다
data가 1이고 ch가 0 → 섬★
data가 1이고 ch가 1 → 이미 체크함

참고로 t1 > 0 &&이랑 t2 > 0 &&도 그냥 t1 &&t2 &&로 줄일 수 있음ㅋㅋ


(프로책팔이) #13

Leetcode 에도 똑같은 문제가 있더군요.

참고로 자바로 짰습니다.

class Solution {
 public  int numIslands(char[][] grid) {
        int count = 0;
        for (int row = 0; row < grid.length; row++) {
            for (int col = 0; col < grid[0].length; col++) {
                if (grid[row][col] == '1') {
                    count++;
                   island(grid, row, col);
                }
            }
        }
        return count;
    }

    public  void island(char[][] grid, int row, int col) {
        if (0 <= row && row < grid.length && 0 <= col && col < grid[0].length && grid[row][col] == '1') {
            grid[row][col] = '0';
            island(grid, row - 1, col);
            island(grid, row + 1, col);
            island(grid, row, col - 1);
            island(grid, row, col + 1);

        }
       
    }
}

(sloth) #14

다른분들 말처럼 visited 필요ㅇ벗이 grid를 걍 0으로 채워버려도되고,
근데 님이 하는거는 bfs가 아니라 dfs 아닌가요 ㅎ
bfs로 풀어보고 disjoint set 써서도 한번 풀어보세요