[알고리즘] 백준 4963번 섬의개수 :: 우유

https://www.acmicpc.net/problem/4963

4963번: 섬의 개수

---

단순한 BFS문제이다. 동서남북만 생각해주는것이 아니라 대각선 방향까지 생각해줘야하기떄문에 
dy, dx 배열을 8가지 방향으로 나눠서 생각해야 했다. 

static 변수랑 BFS 내부에 있는 변수랑 이름을 똑같이 만들어버려서 오랫동안 헤맸다..

---

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 {

    static int w, h, cnt = 0;
    static int map[][];
    static boolean visited[][];
    static int[] dy = {1, 0, -1, 0, 1, 1, -1, -1};
    static int[] dx = {0, 1, 0, -1, 1, -1, 1, -1};

    public static void main(String[] agrs) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = null;
        StringBuilder sb = new StringBuilder();


        while (true) {
            st = new StringTokenizer(br.readLine());
            w = Integer.parseInt(st.nextToken()); // 너비
            h = Integer.parseInt(st.nextToken()); // 높이

            // 입력값 0,0 이 나오면 break
            if (w == 0 && h == 0) break;

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

            // 입력하는대로 map 초기화
            for (int i = 1; i <= h; i++) {
                st = new StringTokenizer(br.readLine());
                for (int j = 1; j <= w; j++) {
                    map[i][j] = Integer.parseInt(st.nextToken());
                }
            }

            for (int i = 1; i <= h; i++) {
                for (int j = 1; j <= w; j++) {
                    if (!visited[i][j] && map[i][j] == 1) {
                        BFS(i, j);
                        cnt++;
                    }
                }
            }

            sb.append(cnt + "\n");

            cnt = 0;
        }

        System.out.println(sb);
    }

    static void BFS(int y, int x) {
        Queue<int[]> qu = new LinkedList<>();
        qu.offer(new int[]{y, x});

        visited[y][x] = true;

        while (!qu.isEmpty()) {
            int curY = qu.peek()[0];
            int curX = qu.peek()[1];

            qu.poll();

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

                if (ny < 1 || nx < 1 || ny > h || nx > w)
                    continue;

                if (visited[ny][nx] || map[ny][nx] == 0)
                    continue;

                visited[ny][nx] = true;
                qu.offer(new int[]{ny, nx});
            }
        }
    }
}