BOJ 4963 섬의 개수

- DFS(x,y,cnt)로 넘겼을 때 0ms

- BFS(x,y,cnt)로 넘겼을 때 4ms

- BFS(x,y)로 넘겼을 때 0ms

 

- w, h의 위치를 잘 보고 입력 받아야 한다.

 

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

 

 

* DFS 풀이

#include <cstdio>
using namespace std;

int map[52][52];
int visited[52][52];

int w,h,cnt;

int dx[8]={-1,0,1,-1,1,-1,0,1};
int dy[8]={1,1,1,0,0,-1,-1,-1};

void dfs(int x, int y, int cnt){
  visited[x][y]=cnt;

  for(int i=0; i<8; i++){
    int nx = x + dx[i];
    int ny = y + dy[i];

    if(nx>=0 && ny>=0 && nx<h && nx<w){
      if(map[nx][ny]==1 && visited[nx][ny]==0){
        dfs(nx,ny,cnt);
      }
    }
  }

  // for(int i=0; i<h; i++){
  //   for(int j=0; j<w; j++){
  //     printf("%d ", visited[i][j]);
  //   }printf("\n");
  // }
}

int main(){
  while(1){
    scanf("%d %d", &w, &h);
    if(w==0 && h==0) break;

    for(int i=0; i<h; i++){
      for(int j=0; j<w; j++){
        scanf("%d", &map[i][j]);
        visited[i][j]=0;
      }
    } //input end

    cnt = 0;
    for(int i=0; i<h; i++){
      for(int j=0; j<w; j++){
        if(map[i][j]==1 && visited[i][j]==0){
          dfs(i,j,++cnt);
        }
      }
    }
    //output field
    printf("%d\n", cnt);
  } //while end
}

 

 

 

* BFS 풀이

#include <cstdio>
#include <queue>
using namespace std;

int map[52][52];
int visited[52][52];

int w,h,cnt;

int dx[8]={-1,0,1,-1,1,-1,0,1};
int dy[8]={1,1,1,0,0,-1,-1,-1};

void bfs(int x, int y){
  queue<pair<int, int> > q;
  q.push(make_pair(x,y));
  visited[x][y]=1;

  while(!q.empty()){
    x = q.front().first;
    y = q.front().second;
    q.pop();

    for(int i=0; i<8; i++){
      int nx = x + dx[i];
      int ny = y + dy[i];

      if(nx>=0 && ny>=0 && nx<h && ny<w){
        if(map[nx][ny]==1 && visited[nx][ny]==0){
          q.push(make_pair(nx,ny));
          visited[nx][ny]=1;
        }
      }
    }
  }
}

int main(){
  while(1){
    scanf("%d %d", &w, &h);
    if(w==0 && h==0) break;

    for(int i=0; i<h; i++){
      for(int j=0; j<w; j++){
        scanf("%d", &map[i][j]);
        visited[i][j]=0;
      }
    } //input end

    cnt = 0;
    for(int i=0; i<h; i++){
      for(int j=0; j<w; j++){
        if(map[i][j]==1 && visited[i][j]==0){
          //dfs(i,j,++cnt);
          bfs(i,j);
          cnt++;
        }
      }
    }
    //output field
    printf("%d\n", cnt);
  } //while end
}