백준 No.4963 섬의 개수- JAVA

문제

정사각형으로 이루어져 있는 섬과 바다 지도가 주어진다. 섬의 개수를 세는 프로그램을 작성하시오

한 정사각형과 가로,세로 또는 대각선으로 연결되어 있는 사각형은 걸어갈 수 있는 사각형이다.

두 정사각형이 같은 섬에 있으려면 한 정사각형에서 다른 정사각형으로 걸어서 갈 수 있는 경로가 있어야 한다. 지도는 바다로 둘러싸여 있으며, 지도 밖으로 나갈 수 없다.

 

1 1
0
2 2
0 1
1 0
3 2
1 1 1
1 1 1
5 4
1 0 1 0 0
1 0 0 0 0
1 0 1 0 1
1 0 0 1 0
5 4
1 1 1 0 1
1 0 1 0 1
1 0 1 0 1
1 0 1 1 1
5 5
1 0 1 0 1
0 0 0 0 0
1 0 1 0 1
0 0 0 0 0
1 0 1 0 1
0 0

 

 

풀이

bfs로 풀었는데 주의할 게 처음에 dx, dy 배열을 4자리로 했는데 그러면 상하좌우만 계속 탐색하여 답과 다르게 출력된다. 그래서 대각선을 추가하기 위해 8자리로 늘려야한다. 상 하 좌 우 대각선 우하,우상,좌하,좌우  이렇게 하는데 순서는 상관없지만 대각선은 각 4개를 다 갈 수 있도록 만들어줘야한다. 

static int dx[] =  {0, 0, -1 ,1, -1, 1, -1, 1};
static int dy[] = {-1, 1, 0, 0, 1, 1, -1, -1};

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 boolean visited[][];
    static int map[][];
    static int W;
    static int H;
    static int dx[] =  {0, 0, -1 ,1, -1, 1, -1, 1};
    static int dy[] = {-1, 1, 0, 0, 1, 1, -1, -1};

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        StringBuilder sb =new StringBuilder();
        String str;
        while( !(str = br.readLine()).equals("0 0") ) {
            st = new StringTokenizer(str);

            W = Integer.parseInt(st.nextToken());
            H = Integer.parseInt(st.nextToken());



            map = new int[H][W];
            visited = new boolean[H][W];
            for (int i = 0; i < H; i++) {
                String temp = br.readLine();
                st = new StringTokenizer(temp);
                for (int j = 0; j < W; j++) {
                    map[i][j] = Integer.parseInt(st.nextToken());
                }
            }

            int count = 0;
            for (int i = 0; i < H; i++) {
                for (int j = 0; j < W ; j++) {
                    if (!visited[i][j] && map[i][j] == 1){
                        bfs(i,j);
                        count++;
                    }
                }
            }
            sb.append(count).append("\n");
        }
        System.out.println(sb);
    }

    public static void bfs(int h,int w){
        Queue<Node> queue = new LinkedList<>();
        queue.add(new Node(h,w));
        visited[h][w] = true;

        while (!queue.isEmpty()){
            Node now = queue.poll();

            for (int i = 0; i < 8 ; i++) {
                int nextH = now.h + dy[i];
                int nextW = now.w + dx[i];

                if(nextW >= 0 && nextW < W && nextH >= 0 && nextH < H){
                    if(!visited[nextH][nextW] && map[nextH][nextW] == 1){
                        visited[nextH][nextW] = true;
                        queue.add(new Node(nextH,nextW));
                    }
                }
            }
        }
    }


    static class Node{
        int h;
        int w;

        public Node(int h,int w){
            this.h = h;
            this.w = w;
        }
    }
}