[ 백준 4963 ] 섬의 개수

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

4963번: 섬의 개수

2. 문제 

3. 문제 요약

주어진 2차원 배열에서, 조건을 만족하는 집합의 수를 찾는 문제이다.

상하좌우 또는 대각선으로 연결되어 있으면, 하나의 덩어리로 보면 된다.

 

 

4. 문제 풀이

(1) 배열 선언 
 2차원 배열임은 쉽게 알 수 있고, 주어지는 데이터가 0 또는 1이니 boolean형으로 하면 메모리를 절약하면서 쉽게 표현할 수 있다.

 배열의 크기에 따라 접근 가능한지 체크를 하지 않기 위해서, 배열의 크기를 [H+2][W+2]로 두고, 외곽의 점들은 default 초기화 값인 (False)가 되도록 처리했다.

 

(2) DFS

 한 사각형과 이어져 있는 모든 사각형들이 하나의 집합(섬) 이므로,
 아직 어느 섬에도 소속되지 않은 섬을 발견했다면, 그 섬에 이어져있는 모든 섬들(인접 8개 영역)을 방문해서 처리하도록 DFS를 사용했다.

 

(3) 연산속도 개선

 처음에는 인접 노드를 방문할때 사용할 d를 {-1, 0, 1 }만을 이용해서 연산을 시켰었는데, 

 dr과 dc를 나누어서 /, % 연산을 최대한 사용하지 않는 방향으로 바꿨다. 

사실 이부분은 알고리즘자체가 변하는 건 아니여서, 가독성&편의와 성능 사이에서 취향에 맞는걸 택하면 될 것 같다.

public static void dfs(int r, int c) {
    int[] d = { -1, 0, 1};
    for (int i = 0; i < 9; i++) {
        int nr = r + d[i/3];
        int nc = c + d[i%3];
        if (map[nr][nc]) {
            map[nr][nc] = false;
            dfs(nr, nc);
        }
    }
}

 

5. 풀이 코드

static BufferedReader bfr = new BufferedReader(new InputStreamReader(System.in));tatic int[] dr = { -1, -1, -1, 0, 0, 1, 1, 1 };
static int[] dc = { -1, 0, 1, -1, 1, -1, 0, 1 };
static boolean[][] map;
static BufferedReader bfr = new BufferedReader(new InputStreamReader(System.in));
static BufferedWriter bfw = new BufferedWriter(new OutputStreamWriter(System.out));
    
public static void problem4963() throws Exception {
    while (true) {
        StringTokenizer str = new StringTokenizer(bfr.readLine());
        int W = Integer.parseInt(str.nextToken());
        int H = Integer.parseInt(str.nextToken());
        if (W == 0) break;
 
        makeMap(W, H);
 
        int ans = 0;
        for (int h = 1; h <= H; h++)
            for (int w = 1; w <= W; w++)
                if (map[h][w]) { dfs(h, w); ans++; }
        bfw.write(ans + "\n");
    }
    bfw.flush();
}
public static void makeMap(int W, int H) throws Exception {
        map = new boolean[H + 2][W + 2];
        for (int h = 1; h <= H; h++) {
            String s = bfr.readLine();
            for (int w = 1; w <= W; w++)
                map[h][w] = s.charAt((w - 1) * 2) > '0';
        }
}
public static void dfs(int r, int c) {
    for (int i = 0; i < 8; i++) {
        int nr = r + dr[i];
        int nc = c + dc[i];
        if (map[nr][nc]) {
            map[nr][nc] = false;
            dfs(nr, nc);
        }
    }
}