99클럽 코테 스터디 6일차 TIL - 섬의 개수 (백준 4963번)

오늘의 학습 키워드

- DFS

- 2차원 배열 탐색

- 8방향 탐색

- 섬의 개수

---

공부한 내용 정리

오늘은 백준 4963번 “섬의 개수” 문제를 풀었다.

이 문제는 지도의 정보가 2차원 배열 형태로 주어지고, 섬(1로 표시된 영역)의 개수를 세는 문제다.

단순히 상하좌우만 보는 것이 아니라, 대각선까지 포함한 8방향을 모두 확인해야 한다.

 

접근 방식:

1. 입력을 받아 지도를 구성.

2. 지도 전체를 순회하며 아직 방문하지 않은 섬(1)을 만나면 DFS로 연결된 모든 땅을 방문 처리.

3. 이 과정을 반복하면서 섬의 개수를 새기.

 

소스코드

import java.util.Scanner;

public class Main {
    static int w, h;
    static int[][] map;
    static boolean[][] visited;

    // 8방향 (상, 하, 좌, 우, 대각선 4방향)
    static int[] dx = {-1, -1, -1, 0, 0, 1, 1, 1};
    static int[] dy = {-1, 0, 1, -1, 1, -1, 0, 1};

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        while (true) {
            w = sc.nextInt();
            h = sc.nextInt();
            if (w == 0 && h == 0) break;

            map = new int[h][w];
            visited = new boolean[h][w];

            for (int i = 0; i < h; i++) {
                for (int j = 0; j < w; j++) {
                    map[i][j] = sc.nextInt();
                }
            }

            int count = 0;
            for (int y = 0; y < h; y++) {
                for (int x = 0; x < w; x++) {
                    if (map[y][x] == 1 && !visited[y][x]) {
                        dfs(x, y);
                        count++;
                    }
                }
            }

            System.out.println(count);
        }

        sc.close();
    }

    static void dfs(int x, int y) {
        visited[y][x] = true;

        for (int dir = 0; dir < 8; dir++) {
            int nx = x + dx[dir];
            int ny = y + dy[dir];

            if (nx >= 0 && ny >= 0 && nx < w && ny < h) {
                if (map[ny][nx] == 1 && !visited[ny][nx]) {
                    dfs(nx, ny);
                }
            }
        }
    }
}

---

오늘의 회고

• 어떤 문제가 있었고, 나는 어떤 시도를 했는지

처음에는 상하좌우만 탐색하는 방식으로 섬의 개수를 세었기 때문에, 대각선으로 연결된 섬을 제대로 인식하지 못하는 문제가 발생했다.

• 어떻게 해결했는지

대각선 방향까지 포함한 총 8방향 탐색 배열을 따로 정의하고, 이를 DFS 탐색에 적용하여 모든 방향을 탐색할 수 있도록 수정했다.

• 무엇을 새롭게 알았는지

지도 탐색 문제에서 방향 배열 설정이 핵심이라는 점을 깨달았다. 단순히 상하좌우만 생각해서는 안 되고, 문제 조건에 맞게 8방향까지 고려해야 할 수 있다.

• 내일 학습할 것은 무엇인지

동일한 문제를 BFS 방식으로도 해결해보며 DFS와의 차이점(예: 메모리 사용량, 탐색 순서, 구현 편의성 등)을 비교해볼 계획이다.