[C++/BOJ] 백준 4963 섬의 개수(BFS)

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

4963번: 섬의 개수

• 이 문제의 특별한 점

      1 . 대각선으로 이어지는 것도 고려해야한다.

      2 . 0을 두개 입력받으면 반복문이 종료되어야한다.

 

 

 

1. 대각선으로 이어지는 것도 고려해야한다.

그림을 그려서 대각선까지 갈 수 있도록 dx, dy를 만든다. [배열의 크기는 8] 

 

( i , j ) 를 중심으로 8개의 칸을 생각한다.

8개의 칸 중 하나의 칸을 선택해 돌려가면서 dx는 i의 값을 , dy 는 j의 값으로 배열을 만들어준다.

 

좌측 왼쪽의 칸을 선택해 시계방향으로 돌아가면서 만든 dx, dy 배열이다. 

---

 

     2 .  0을 두개 입력받으면 반복문이 종료되어야한다.

 

별로 어렵지는 않지만 어째선지 처음 만들었던 코드가 틀렸다.

if (w == h == 0) break; // 처음 만든 코드 // 틀림
if ((w <= 0) || (h <= 0)) break; // 맞은 코드

x == y == 0 이런 식으로 비교는 안되나보다!  오늘 또 하나 배웠다.

 

 

 

---

 

 

 

• 문제의 정답  코드 

#include<iostream>
#include<queue>
 #include<cstring>
using namespace std;
int dx[] = { -1,-1,-1,0,1,1,1,0 };
int dy[] = { -1,0,1,1,1,0,-1,-1,};
#define x first
#define y second
int map[51][51];
int check[51][51];
queue<pair<int, int> > q;
int cnt;
int w, h;
void bfs() {
    while (!q.empty()) {
        pair<int, int> tmp = q.front();
        int x = tmp.first;
        int y = tmp.second;
        q.pop();
        for (int i = 0; i < 8; i++) {
            int nx = dx[i] + x;
            int ny = dy[i] + y;
            if (nx < 0 || nx >= h || ny < 0 || ny >= w ) continue;
            if (check[nx][ny] == 1 || map[nx][ny] == 0) continue;
            check[nx][ny] = 1;
            q.push({ nx,ny });
        }

    }
}
int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
  
    while(1) {
        cin >> w >> h;
       // if (w == h == 0) break;
        if ((w <= 0) || (h <= 0)) break;
        for (int i = 0; i < h; i++) {
            for (int j = 0; j < w; j++) {
                cin >> map[i][j];
            }
        }
        for (int i = 0; i < h; i++) {
            for (int j = 0; j < w; j++) {
                if (map[i][j] == 1 && check[i][j] == 0) {
                    cnt++;
                    q.push({ i,j });
                    check[i][j] = 1;
                    bfs();
                }

            }
        }
        cout << cnt << "\n";
        cnt = 0;
        memset(check, 0, sizeof(check));
    }
}