백준 4963 풀이

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

예전에 풀었던 백준 "유기농 배추" 문제의 확장판이다.

참고

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

이전에 풀었던 유기농 배추 문제와 차이점은 대각선으로 연결된 곳도 하나의 영역으로 포함된다는 점이다. 따라서 그 부분만 위의 문제에서 조정해주면 쉽게 해결이 되었다.

dx, dy 배열부분이 달라졌는데 원래 현재 방문한 위치에서 상하좌우만 탐색하면 되는 것을 대각선 부분도 포함해서 탐색해야하기 때문에 변경했다.

import java.io.*;

public class Main {
    static int count = 0;
    static int index = 0;
    static int[] dx = {-1, 1, 0, 0, -1, -1, 1, 1};
    static int[] dy = {0, 0, -1, 1, -1, 1, -1, 1};
    static boolean visit[][];
    static int n, m;
    static int graph[][];


    public static void main(String[] args) throws IOException {
        // write your code here
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        while (true) {
            count = 0;
            String line = br.readLine();
            String[] tmp = line.split(" ");
            n = Integer.parseInt(tmp[0]);
            m = Integer.parseInt(tmp[1]);
            graph = new int[m][n];
            visit = new boolean[m][n];
            for (int h = 0; h < m; h++) {
                for (int j = 0; j < n; j++) {
                    visit[h][j] = false;
                }
            }

            if (n == 0 && m == 0)
                break;
            for (int i = 0; i < m; i++) {
                String l = br.readLine();
                String[] t = l.split(" ");
                for (int j = 0; j < t.length; j++) {
                    int a = Integer.parseInt(t[j]);
                    graph[i][j] = a;
                }
            }
            find();
            bw.write(Integer.toString(count)+"\n");
        }

        br.close();
        bw.close();
    }

    public static void find() {
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (graph[i][j] == 1 && visit[i][j] == false) {
                    //					apts.add(0);
                    bfs(i, j);
                    count++;
                    index++;
                }
            }

        }
    }

    public static void bfs(int x, int y) {
        visit[x][y] = true;

        for (int i = 0; i < 8; i++) {
            if ((x + dx[i] >= 0 && x + dx[i] <= m - 1) && (y + dy[i] >= 0 && y + dy[i] <= n - 1)) {
                if (graph[x + dx[i]][y + dy[i]] == 1 && !visit[x + dx[i]][y + dy[i]])
                    bfs(x + dx[i], y + dy[i]);
            }
        }
    }
}