[백준(BOJ)] 4963번 : 섬의 개수 - C++[CPP]

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

4963번: 섬의 개수

---

⊙ 문제

⊙ 입력

⊙ 출력

⊙ 예제 입출력

⊙ 알고리즘 분류

• 그래프 이론
• 그래프 탐색
• 너비 우선 탐색
• 깊이 우선 탐색

 

---

 

⊙ 문제 접근 과정

 

다른 bfs와 비슷하지만 이번에는 대각선까지 고려해주어야 한다.

상, 하, 좌, 우, 우상, 우하, 좌하, 좌상. 총 8개의 방향을 탐색해 방문 체크해주었다.

그리고 reset() 함수를 직접 만들어주어 결괏값을 출력하면 계속 리셋해주고 반복해주었다.

---

 

⊙ 문제 풀이

 

#include <iostream>
#include <queue>

using namespace std;
#define MAX 52

int w,h;
int cnt=0;
int arr[MAX][MAX];
int visited[MAX][MAX];
int dw[] = {1,0,-1,0,1,-1,1,-1};
int dh[] = {0,1,0,-1,1,1,-1,-1};
queue<pair<int,int>> q;

void reset() {
	while (!q.empty()) q.pop();
	for (int i = 0; i < h; i++) {
		for (int j = 0; j < w; j++) {
			visited[i][j] = 0;
			arr[i][j] = 0;
            cnt=0;
		}
	}
}

void bfs(int h,int w) {
    q.push({h,w});
    while(!q.empty()) {
        int a = q.front().first;
        int b = q.front().second;
        q.pop();
        visited[h][w]=true;
        for(int i=0;i<8;i++) {
            int nh = a + dh[i];
            int nw = b + dw[i];
            if(0<=nh && 0<=nw && nh <MAX && nw < MAX && !visited[nh][nw]&& arr[nh][nw]==1) {
                q.push({nh,nw});
                visited[nh][nw]=true;
            }
        }
    }
}

int main() {
    while(true) {
        cin >> w >> h;
        if(!w&&!h) break;

        for(int i=0;i<h;i++) {
            for(int j=0;j<w;j++) {
                cin >> arr[i][j];
            }
        }

        for(int i=0;i<h;i++) {
            for(int j=0;j<w;j++) {
                if(arr[i][j]&&!visited[i][j]) {
                    bfs(i,j);
                    cnt++;
                }
            }
        }

        cout << cnt << " ";
        reset();
    }
}

---

⊙ 결과

 

---

⊙ 마무리

 

 

NONE

 

좋아요는 로그인하지 않아도 누를 수 있습니다!