[백준/JAVA] 4963번: 섬의 개수

📖 문제

4963번: 섬의 개수

 

 

💡  풀이 방식

• BFS

 

w와 h가 0이 아닐 때만 아래와 같이 진행한다.

 

1. 격자의 값을 입력받는다.2. 모든 점을 탐색하며 방문하지 않은 땅에 대해 BFS 탐색을 실행하고, 섬 개수를 증가시킨다.  - BFS 탐색: 격자 범위를 벗어나지 않고, 방문한 적 없고, 땅(1)인 값에 대해 8방향 탐색 수행 (상하좌우 + 대각선 4방향) 3. 구한 섬 개수를 출력한다.

 

 

🔺 코드

import java.util.*;
import java.io.*;
 
public class Main {
    static int[] dx = {-1,1,0,0, -1,-1,1,1}; // 8방향 탐색 (상하좌우 + 대각선)
    static int[] dy = {0,0,-1,1, -1,1,-1,1};
    
    static int w,h;
    static int[][] map;
    static boolean[][] visited;
    static StringBuilder sb = new StringBuilder();
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        
        while(true) {
            st = new StringTokenizer(br.readLine(), " ");
            
            w = Integer.parseInt(st.nextToken());   // 너비 = 열
            h = Integer.parseInt(st.nextToken());   // 높이 = 행
            
            if(w == 0 && h == 0) {
                break;
            }
            
            map = new int[h][w];
            for(int i = 0 ; i < h ; i++) {
                st = new StringTokenizer(br.readLine(), " ");
                for(int j = 0 ; j < w ; j++) {
                    map[i][j] = Integer.parseInt(st.nextToken());
                }
            }
            
            visited = new boolean[h][w];
            int cnt = 0;
            
            for(int i = 0 ; i < h ; i++) {
                for(int j = 0 ; j < w ; j++) {
                    if(!visited[i][j] && map[i][j] == 1) {  // 1: 땅
                        bfs(i,j);
                        cnt++;
                    }
                }
            }
            
            sb.append(cnt).append("\n");
        }
        
        System.out.println(sb.toString());
    }
    
    private static void bfs(int x, int y) {
        Queue<int[]> q = new ArrayDeque<>();
        q.add(new int[] {x, y});
        visited[x][y] = true;
        
        while(!q.isEmpty()) {
            int[] now = q.poll();
            
            for(int d = 0 ; d < 8 ; d++) {
                int nx = now[0] + dx[d];
                int ny = now[1] + dy[d];
                
                if(nx < 0 || nx >= h || ny < 0 || ny >= w)  continue;
                
                if(!visited[nx][ny] && map[nx][ny] == 1) { // 방문하지 않은 땅 걸으러 가기
                    visited[nx][ny] = true;
                    q.add(new int[] {nx, ny});   
                }
            }
        }
    }
}
 

 

 

 

➕ 다른 풀이 방식

DFS로도 풀 수 있다.

[DFS] 백준 - 4963번: 섬의 개수 Java 풀이

---

 

 

1회독	2회독	3회독	4회독	5회독
V