99클럽 코테 스터디 6일차 TIL + 섬의 개수

 

- 오늘의 학습 키워드

섬의 개수

- 풀이

import java.util.Scanner;

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

    // 8방향 (상, 하, 좌, 우 + 대각선)
    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 i = 0; i < h; i++) {
                for (int j = 0; j < w; j++) {
                    if (map[i][j] == 1 && !visited[i][j]) {
                        DFS(i, j);
                        count++;
                    }
                }
            }
            System.out.println(count);
        }
    }

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

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

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

        }
    }
}

- 오늘의 회고

지도 전체를 돌면서 아직 방문하지 않은 땅(1)을 발견하면 DFS를 시작하고, 연결된 모든 땅을 방문 처리한 뒤 섬의 개수를 증가시키는 방식으로 구현했다.

상하좌우뿐 아니라 대각선까지 연결되는 경우까지 해서 방향 배열을 8개 만든 다음 탐색!

확실히 4개, 8개 좌표는 외워 두는 게 좋을 듯 하댜