[백준] 4963 섬의 개수 c++

 

문제 링크 https://www.acmicpc.net/problem/4963

Key

• 대각선까지 총 8방향을 탐색해야 하는 문제이다.
• 그것 외에는 다른 DFS,BFS유형의 문제들과 유사하게 순회 시 카운트를 증가하는 유형이기 때문에 쉽게 접근할 수 있었다.
• height이 열, width이 행을 뜻하기 때문에 입력을 height, width순으로 받아야 한다.

 

1. DFS풀이

#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
#include<cstring>
const int MAX = 51;
using namespace std;
int n;
int arr[MAX][MAX];
bool visited[MAX][MAX];
int dir[8][2] = { {-1,0},{1,0},{0,1},{0,-1},{-1,1},{-1,-1},{1,-1},{1,1} };
int w, h;
 
void dfs(int x, int y) {
    for (int i = 0; i < 8; i++) { //8방향 탐색
        int nx = x + dir[i][0];
        int ny = y + dir[i][1];
        if (nx < 0 || nx >= w || ny < 0 || ny >= h)
            continue;
        if (visited[nx][ny])
            continue;
        if (arr[nx][ny] == 0)
            continue;
        visited[nx][ny] = true;
        dfs(nx, ny);
    }
}
int main()
{
    while (1) {
        int cnt = 0;
        memset(visited, false, sizeof(visited));
 
        cin >> h >> w;
        if (w == 0 && h == 0) //종료조건
            break;
 
        for (int i = 0; i < w; i++) {
            for (int j = 0; j < h; j++) {
                cin >> arr[i][j];
            }
        }
        for (int i = 0; i < w; i++) {
            for (int j = 0; j < h; j++) {
                if (arr[i][j] == 1 && !visited[i][j]) {
                    visited[i][j] = true;
                    dfs(i, j);
                    cnt++;
                }
            }
        }
        cout << cnt << endl;
    }
}
 

 

2. BFS풀이

#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
#include<cstring>
using namespace std;
const int MAX = 51;
int dir[8][2] = { {-1,0},{1,0},{0,1},{0,-1},{1,1},{1,-1},{-1,1},{-1,-1} };
int w, h;
int arr[MAX][MAX];
bool visited[MAX][MAX];
void bfs(int x, int y) {
    queue<pair<int, int>> q;
    q.push({ x,y });
 
    while (!q.empty()) {
        int cx = q.front().first;
        int cy = q.front().second;
        q.pop();
 
        for (int i = 0; i < 8; i++) {
            int nx = cx + dir[i][0];
            int ny = cy + dir[i][1];
            if (visited[nx][ny])
                continue;
            if (nx < 0 || nx >= h || ny < 0 || ny >= w)
                continue;
            if (arr[nx][ny] == 0)
                continue;
 
            visited[nx][ny] = true;
            q.push({ nx,ny });
        }
    }
}
int main(void) {
    while (1) {
        cin >> w >> h;
        int answer = 0; //갯수 초기화
        memset(visited, false, sizeof(visited)); //방문배열 초기화
        if (w == 0 && h == 0)
            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 (visited[i][j] == 0 && arr[i][j] == 1) {
                    bfs(i, j);
                    answer++; //bfs순회를 시작할때마다 카운트 증가
                }
            }
        }
        cout << answer << endl;
    }
}