(8) [C++, Java] 백준 No.4963 : 섬의 개수

문제

풀이

자세한 풀이 : https://ldgeao99.tistory.com/400

 

# C++(DFS)

#include <iostream>
using namespace std;

int place[51][51];  // 0 : 바다, 1 : 섬
int check[51][51];  // 0 : 방문안함, 1이상 : 섬의 번호
int dx[8] = {0, -1, -1, -1, 0, 1, 1, 1};
int dy[8] = {-1, -1, 0, 1, 1, 1, 0, -1};
int w, h;

//인접한 모든 섬을 탐색하고, 번호를 부여함
void dfs(int i, int j, int num){
    check[i][j] = num;

    // 8개의 방향중에 갈 수 있는 경우, 그리고 방문하지 않은 경우에만 탐색
    for(int k = 0; k < 8; k++){
        int x = i + dx[k];
        int y = j + dy[k];
        
        if(x>=1 && x<=h && y>=1 && y <= w){
            if (place[x][y] == 1 && check[x][y] == 0){
                dfs(x, y, num);
            }
        }
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    while(true)
    {
        //가로세로 입력받기
        cin >> w >> h;
        if (w == 0 && h == 0)
            break;

        //배열 사용전 초기화
        for (int i = 1; i <= h; i++){
            for (int j = 1; j <= w; j++){
                place[i][j] = 0;
                check[i][j] = 0;
            }
        }

        //땅, 바다 정보 입력받기
        for (int i = 1; i <= h; i++){
            for (int j = 1; j <= w; j++){
                cin >> place[i][j];
            }
        }

        //모든 점을 시작점으로 하여 탐색 진행, 연결된 섬인 경우에 같은 번호 부여
        int num = 0;
        for (int i = 1; i <= h; i++){
            for (int j = 1; j <= w; j++){
                if (place[i][j] == 1 && check[i][j] == 0)
                    dfs(i, j, ++num);
            }
        }
        
        cout << num << "\n";
    } 
}

# C++(BFS)

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

int place[51][51];  // 0 : 바다, 1 : 섬
int check[51][51];  // 0 : 방문안함, 1이상 : 섬의 번호
int dx[8] = {0, -1, -1, -1, 0, 1, 1, 1};
int dy[8] = {-1, -1, 0, 1, 1, 1, 0, -1};
int w, h;

//인접한 모든 섬을 탐색하고, 번호를 부여함
void bfs(int i, int j, int num){
    queue<pair<int, int>> q;

    q.push(make_pair(i, j));
    check[i][j] = num;

    while(!q.empty()){
        pair<int, int> p = q.front();
        q.pop();
        i = p.first;
        j = p.second;

        // 8개의 방향중에 갈 수 있는 경우, 그리고 방문하지 않은 경우에만 탐색
        for(int k = 0; k < 8; k++){
            int x = i + dx[k];
            int y = j + dy[k];
        
            if(x>=1 && x<=h && y>=1 && y <= w){
                if (place[x][y] == 1 && check[x][y] == 0){
                    check[x][y] = num;
                    q.push(make_pair(x, y));
                }
            }
        }
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    while(true)
    {
        //가로세로 입력받기
        cin >> w >> h;
        if (w == 0 && h == 0)
            break;

        //배열 사용전 초기화
        for (int i = 1; i <= h; i++){
            for (int j = 1; j <= w; j++){
                place[i][j] = 0;
                check[i][j] = 0;
            }
        }

        //땅, 바다 정보 입력받기
        for (int i = 1; i <= h; i++){
            for (int j = 1; j <= w; j++){
                cin >> place[i][j];
            }
        }

        //모든 점을 시작점으로 하여 탐색 진행, 연결된 섬인 경우에 같은 번호 부여
        int num = 0;
        for (int i = 1; i <= h; i++){
            for (int j = 1; j <= w; j++){
                if (place[i][j] == 1 && check[i][j] == 0)
                    bfs(i, j, ++num);
            }
        }
        
        cout << num << "\n";
    } 
}

# Java

import java.util.*;

class Pair {
    int x;
    int y;
    Pair(int x, int y) {
        this.x = x;
        this.y = y;
    }
}

public class Main {
    public static final int[] dx = {0, 0, 1, -1, 1, 1, -1, -1};
    public static final int[] dy = {1, -1, 0, 0, 1, -1, 1, -1};
    public static void bfs(int[][] a, int[][] group, int x, int y, int cnt, int n, int m) {
        Queue<Pair> q = new LinkedList<Pair>();
        q.add(new Pair(x, y));
        group[x][y] = cnt;
        while (!q.isEmpty()) {
            Pair p = q.remove();
            x = p.x;
            y = p.y;
            for (int k=0; k<8; k++) {
                int nx = x+dx[k];
                int ny = y+dy[k];
                if (0 <= nx && nx < n && 0 <= ny && ny < m) {
                    if (a[nx][ny] == 1 && group[nx][ny] == 0) {
                        q.add(new Pair(nx, ny));
                        group[nx][ny] = cnt;
                    }
                }
            }
        }
    }
    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        while (true) {
            int m = sc.nextInt();
            int n = sc.nextInt();
            if (n == 0 && m == 0) {
                break;
            }
            int[][] a = new int[n][m];
            for (int i=0; i<n; i++) {
                for (int j=0; j<m; j++) {
                    a[i][j] = sc.nextInt();
                }
            }
            int cnt = 0;
            int[][] group = new int[n][m];
            for (int i=0; i<n; i++) {
                for (int j=0; j<m; j++) {
                    if (a[i][j] == 1 && group[i][j] == 0) {
                        bfs(a, group, i, j, ++cnt, n, m);
                    }
                }
            }
            System.out.println(cnt);
        }
    }
}