[백준] 4963번 섬의 갯수

문제

정사각형으로 이루어져 있는 섬과 바다 지도가 주어진다. 섬의 개수를 세는 프로그램을 작성하시오.

한 정사각형과 가로, 세로 또는 대각선으로 연결되어 있는 사각형은 걸어갈 수 있는 사각형이다. 

두 정사각형이 같은 섬에 있으려면, 한 정사각형에서 다른 정사각형으로 걸어서 갈 수 있는 경로가 있어야 한다. 지도는 바다로 둘러싸여 있으며, 지도 밖으로 나갈 수 없다.

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다.

둘째 줄부터 h개 줄에는 지도가 주어진다. 1은 땅, 0은 바다이다.

입력의 마지막 줄에는 0이 두 개 주어진다.

출력

각 테스트 케이스에 대해서, 섬의 개수를 출력한다.

 

나는 이 문제를 bfs로 풀었다. 애초에 bfs가 dfs보다 최소값을 찾는데 유용하기 때문에 bfs를 먼저 공부해 두는게 좋다고 생각이 들었다. 어제 보다 빨리 푼 느낌이 들어서 좋았다. 물론... 문제를 풀면서 마지막에 막히긴 했지만, 전체적인 맥락은 맞은것 같아 다행이라는 생각이든다.

 

#include <bits/stdc++.h>
#define MAX 50
using namespace std;
int w,h;
int dist[MAX][MAX];
bool visit[MAX][MAX];
int dx[8] = {1,-1,0,0,1,1,-1,-1};
int dy[8] = {0,0,-1,1,1,-1,-1,1};
int ans = 0;
void bfs(int i, int j) {
          queue<int> q1 ;queue<int> q2;
          q1.push(i);    q2.push(j);
          visit[i][j] = true;

          while(!q1.empty() && !q2.empty()) {
              int x = q1.front();
              int y = q2.front();

              q1.pop(); q2.pop();

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

                if (0 > nx || h<=nx) {
                  continue;
                } 

                if (0 > ny || w<=ny) {
                  continue;
                }

                if (dist[nx][ny] == 1 && !visit[nx][ny]) {
                  q1.push(nx);q2.push(ny);
                  visit[nx][ny] = true;
                }
              }
          }
                    ans++;
}
int main(void) {
     ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
  while(true) {
  cin >> w >> h;
  
  if (w == 0 && h == 0) {
    return 0;
  }

  for(int i = 0;i<MAX;i++) {
    memset(dist[i],0,sizeof(dist[i]));
    memset(visit[i],false,sizeof(visit[i]));
  }

  for(int i = 0;i<h;i++) {
    for(int j = 0; j<w;j++) {
      cin >> dist[i][j];
    }
  }
  ans = 0;
  for(int i = 0; i<h;i++) {
    for(int j = 0;j<w;j++) {
      if (dist[i][j] == 1 && !visit[i][j]) {
        bfs(i,j);
      }
    }
  }
  cout << ans << "\n";
  }
}
     

오늘 define과 memset을 학습했다!

처음에는 값을 찾는 부분을 메인문에서 하지 않았고, bfs안에서 진행하였다. 그러다 보니 꼬이는 듯한 느낌을 받았다. 왜냐하면 그렇게 되면 반복문이 3개가 겹쳐지기 때문에 코딩하는 나로써 쉽지 않겠다는 생각이 들었다. 그래서 밑으로 옮겼다.

 

잘 모르지만  memset은 줄전체를 초기화 시키는 느낌이 들었다. 그냥 그렇다. 또, 전체 사이즈를 구하는 것 같다. 그러는 와중에 sizeof를 하면 1차원 배열의 크기를 알 수 있는 것 같다.

 

내가 처음 실수한 부분이 이건데 h  와 w다. h 줄인걸 알고 있음에도 위에다 작성하고 w는 행인걸 알면서도 밑에다 작성하였다. 이게 내 실수 였다. 이제 반복하지 말아야 겠다고 다짐한다.

 

 

ios_base::sync_with_stdio(false);

cin.tie(NULL); cout.tie(NULL);

 

이거 안해놓으면 값 입력 될때마다 값이 출력되기 때문에 굉장히 귀찮다.ㅎㅎ

뭐 때문인지는 더 공부해야 알 것 같은데, 아무튼... 이번엔 저 3개로 퉁쳐야지 ㅎㅎ

 

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

int n,m;
int a[55][55];

void bfs(int x, int y){
    queue<int> qx, qy;
    qx.push(x);
    qy.push(y);
    a[x][y] = 0;
    while (!qx.empty()) {
        x = qx.front();
        y = qy.front();
        qx.pop();
        qy.pop();
        for (int i=-1; i<=1; i++) {
            for (int j=-1; j<=1; j++) {
                if(i == 0 && j == 0) continue;
                if(x + i >= n || y + j >= m || x + i < 0 || y + j < 0) continue;
                if(a[x+i][y+j] == 1){
                    a[x+i][y+j] = 0;
                    qx.push(x+i);
                    qy.push(y+j);
                }
            }
        }
    }
}

int main(){
    while (~scanf("%d %d",&m,&n)) {
        if(n == 0 && m == 0) break;
        for (int i=0; i<n; i++) {
            for (int j=0; j<m; j++) {
                scanf("%d",&a[i][j]);
            }
        }
        int cnt = 0;
        for (int i=0; i<n; i++) {
            for (int j=0; j<m; j++) {
                if(a[i][j] == 1) bfs(i,j), cnt++;
            }
        }
        printf("%d\n",cnt);
    }
}

아직은 이 코드를 잘 모르겠다.ㅎㅎ