[BOJ][4963] 섬의 개수

1. 문제 링크

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

2. 사용 알고리즘

DFS

3. 풀이

1) 섬의 존재여부를 저장하기 위한 배열 arr, 방문여부 확인을 위한 배열 check 선언

2) (1, 1)부터 반복문을 돌며, 섬이면서 방문하지 않은 정점부터 DFS 탐색 시작

• 현재 정점의 x - 1, y 좌표가 유효하고, 섬이고, 방문하지 않은 경우 → DFS 탐색 계속 진행

• 현재 정점의 x - 1, y + 1 좌표가 유효하고, 섬이고, 방문하지 않은 경우 → DFS 탐색 계속 진행

• 현재 정점의 x, y + 1 좌표가 유효하고, 섬이고, 방문하지 않은 경우 → DFS 탐색 계속 진행

• 현재 정점의 x + 1, y + 1 좌표가 유효하고, 섬이고, 방문하지 않은 경우 → DFS 탐색 계속 진행

• 현재 정점의 x + 1, y 좌표가 유효하고, 섬이고, 방문하지 않은 경우 → DFS 탐색 계속 진행

• 현재 정점의 x + 1, y - 1 좌표가 유효하고, 섬이고, 방문하지 않은 경우 → DFS 탐색 계속 진행

• 현재 정점의 x, y - 1 좌표가 유효하고, 섬이고, 방문하지 않은 경우 → DFS 탐색 계속 진행

• 현재 정점의 x - 1, y - 1 좌표가 유효하고, 섬이고, 방문하지 않은 경우 → DFS 탐색 계속 진행

4. 소스 코드

4-1. C++

https://github.com/dev-aiden/problem-solving/blob/main/boj/4963.cpp

#include <iostream>

using namespace std;

int w, h;
int arr[53][53];
int check[53][53];
int dx[8] = {-1, -1, 0, 1, 1, 1, 0, -1};
int dy[8] = {0, 1, 1, 1, 0, -1, -1, -1};

void dfs(int y, int x) {
    check[y][x] = 1;
    for(int i = 0; i < 8; ++i) {
        int nx = x + dx[i], ny = y + dy[i];
        if(nx >= 1 && nx <= w && ny >= 1 && ny <= h && arr[ny][nx] && !check[ny][nx]) dfs(ny, nx);
    }
}

int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    while(1) {
        cin >> w >> h;
        if(!w && !h) break;
        for(int i = 1; i <= h; ++i) {
            for(int j = 1; j <= w; ++j) {
                cin >> arr[i][j];
                check[i][j] = 0;
            }
        }
        int ans = 0;
        for(int i = 1; i <= h; ++i) {
            for(int j = 1; j <= w; ++j) {
                if(arr[i][j] && !check[i][j]) {
                    ++ans;
                    dfs(i, j);
                }
            }
        }
        cout << ans << "\n";
    }
    return 0;
}

4-2. JAVA

https://github.com/dev-aiden/problem-solving/blob/main/boj/4963.java

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    
    static int w, h;
    static int[][] arr = new int[53][53];
    static int[][] check = new int[53][53];
    static int dx[] = {-1, -1, 0, 1, 1, 1, 0, -1};
    static int dy[] = {0, 1, 1, 1, 0, -1, -1, -1};

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        while(true) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            w = Integer.parseInt(st.nextToken());
            h = Integer.parseInt(st.nextToken());
            if(w == 0 && h == 0) break;
            for(int i = 1; i <= h; ++i) {
                st = new StringTokenizer(br.readLine());
                for(int j = 1; j <= w; ++j) {
                    arr[i][j] = Integer.parseInt(st.nextToken());
                    check[i][j] = 0;
                }
            }
            int ans = 0;
            for(int i = 1; i <= h; ++i) {
                for(int j = 1; j <= w; ++j) {
                    if(arr[i][j] == 1 && check[i][j] == 0) {
                        ++ans;
                        dfs(i, j);
                    }
                }
            }
            sb.append(ans).append("\n");
        }
        System.out.println(sb);
    }

    static void dfs(int y, int x) {
        check[y][x] = 1;
        for(int i = 0; i < 8; ++i) {
            int nx = x + dx[i], ny = y + dy[i];
            if(nx >= 1 && nx <= w && ny >= 1 && ny <= h && arr[ny][nx] == 1 && check[ny][nx] == 0) dfs(ny, nx);
        }
    }
}