[백준 4963] - [그래프] - 섬의 개수 (JAVA)

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

---

이 문제는 그래프 기본 문제이다. 

DFS 혹은 BFS로 풀면 되고 정답률이 48%로 어렵지 않은 문제이고 그렇기에 간단하게 접근 할 수 있다. 

좌표 기준 가로, 세로,  대각선으로 움직일수 있는 땅을 하나의 섬이라 간주한다고 한다.

한번 탐색할때 가로 세로 뿐만 아니라 대각선으로도 탐색을 진행하면 임의의 좌표 [Y,X] 와 하나의 섬인 경우를 확인할 수 있다.

속도를 줄이기 위해 땅의 좌표들은 입력을 받을때 큐에 저장하였고 큐에서 하나씩 추출해가면서 탐색을 진행했다.

소스

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class Main {
    public static int ROW, COL;
    
    public static int[][] arr;
    public static boolean[][] visited;
    
    public static Queue<int[]> queue;
    
    public static int[]    dy = {-1, 1, 0, 0, -1, -1, 1, 1}; // 상 하 좌 우 좌상 우상, 좌하, 우하
    public static int[] dx = {0, 0, -1, 1, -1, 1, -1, 1}; 
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = null;
        StringBuilder sb = new StringBuilder();
        
        while(true) {
            st = new StringTokenizer(br.readLine());
            
            COL = Integer.parseInt(st.nextToken());
            ROW = Integer.parseInt(st.nextToken());
            
            arr = new int[ROW][COL];
            visited = new boolean[ROW][COL];
            
            queue = new LinkedList<int[]>();
            
            if(COL == 0 && ROW == 0) break;
            
            // 좌표 입력받기
            for(int i=0; i < ROW; i++) {
                st = new StringTokenizer(br.readLine());
                for(int j=0; j < COL; j++) {
                    arr[i][j] = Integer.parseInt(st.nextToken());
                    
                    if(arr[i][j] == 1) queue.offer(new int[] {i, j});
                }
            }
            
            // 큐에서 하나씩 꺼내면서 확인한다.
            int count = 0;
            while(!queue.isEmpty()) {
                int y = queue.peek()[0];
                int x = queue.peek()[1];
                
                queue.poll();
                
                if(visited[y][x]) continue;
                
                DFS(y,x);
                count++;
            }
            sb.append(count + "\n");
        }
        System.out.println(sb.toString());
    }
    
    public static void DFS(int y, int x) {
        visited[y][x] = true;
        
        for(int i=0; i < 8; i++) {
            int yy = y + dy[i];
            int xx = x + dx[i];
            
            if(yy < 0 || xx < 0 || yy >= ROW || xx >= COL) continue;
            if(arr[yy][xx] == 0) continue;
            if(visited[yy][xx]) continue;
            
            DFS(yy, xx);
        }
    }
}