99클럽 코테 스터디 31일차 - bfs

풀이

• 이차원 배열 순회하면서 > 0 인 x, y를 기점으로 8면을 dfs로 탐색함
• visited로 방문하지 않은 곳만 탐색

코드

public class Main {
    static int r, c;
    static int[][] board;
    static boolean[][] visited;
    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);
        
        int r = sc.nextInt();
        int c = sc.nextInt();
        board = new int[r][c];
        visited = new boolean[r][c];
        
        for (int i = 0; i < r; i++) {
            for (int j = 0; j < c; j++) {
                 board[i][j] = sc.nextInt();
            }
        }
        
        int answer = 0;
        for (int i = 0; i < r; i++) {
            for (int j = 0; j < c; j++) {
                if (board[i][j] > 0 && !visited[i][j]) {
                    dfs(i, j);
                    answer++;
                }
            }
        }
        System.out.println(answer);
    }
    
    public static void dfs(int x, int y) {
        visited[x][y] = true;
        
        for (int k = 0; k < 8; k++) {
            int nx = x + dx[k];
            int ny = y + dy[k];
            
            if (nx >= 0 && nx < r && ny >= 0 && ny < c && board[nx][ny] > 0 && !visited[nx][ny]) {
                dfs(nx, ny);
            }
        }
    }
}

정리

• 백준에서 메모리 초과 나오는데 왜 그러지는 모르겠다
• 백준이랑은 안 맞는 듯