[알고리즘-자바] 백준 4963번 섬의 개수

문제

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

4963번: 섬의 개수

언어

자바 JAVA

로직

동서남북 그리고 대각선 체크

dx : 0은 제자리, 1은 오른쪽, -1은 왼쪽

dy : 0은 제자리, 1은 아래쪽, -1은 위쪽

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

섬의 정보 그리고 방문 정보 저장

visited = new boolean[h][w];
graph = new int[h][w];
for (int i = 0; i < h; i++) {
    input = br.readLine().split(" ");
    for (int j = 0; j < w; j++) {
        graph[i][j] = Integer.parseInt(input[j]);
    }
}

탐색 조건

지도 전체를 탐색한다. 현재 위치를 방문한 적이 없으면서 섬일 경우에만 탐색을 한다.

for (int i = 0; i < h; i++) {
    for (int j = 0; j < w; j++) {
        if (!visited[i][j] && graph[i][j] == 1) {
            bfs(graph, new int[]{i, j});
            count++;
        }
    }
}

탐색

현재 위치(curX, curY)에서 동서남북 그리고 대각선을 돌면서 현재위치하고 이어져있는지 확인한다.

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

    for (int i = 0; i < 12; i++) {
        int tmpX = curX + dx[i];
        int tmpY = curY + dy[i];

        if (tmpX >= 0 && tmpX < h && tmpY >= 0 && tmpY < w) {
            if (!visited[tmpX][tmpY] && graph[tmpX][tmpY] == 1) {
                visited[tmpX][tmpY] = true;
                que.offer(new int[]{tmpX, tmpY});
            }
        }
    }
}

---

 

최종 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;

public class Main {
    static boolean[][] visited;
    static int[][] graph;
    static int w, h;
    static int[] dx = {1, 1, 1, -1, -1, -1, 0, -1, 1, 0, -1, 1};
    static int[] dy = {0, -1, 1, 0, -1, 1, -1, -1, -1, 1, 1, 1};

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuffer sb = new StringBuffer();

        while (true) {
            String[] input = br.readLine().split(" ");
            w = Integer.parseInt(input[0]);
            h = Integer.parseInt(input[1]);
            if (w == 0 && h == 0) {
                break;
            }

            visited = new boolean[h][w];
            graph = new int[h][w];
            for (int i = 0; i < h; i++) {
                input = br.readLine().split(" ");
                for (int j = 0; j < w; j++) {
                    graph[i][j] = Integer.parseInt(input[j]);
                }
            }

            int count = 0;
            for (int i = 0; i < h; i++) {
                for (int j = 0; j < w; j++) {
                    if (!visited[i][j] && graph[i][j] == 1) {
                        bfs(graph, new int[]{i, j});
                        count++;
                    }
                }
            }
            sb.append(count + "\n");
        }

        System.out.println(sb);
    }

    static void bfs(int[][] graph, int[] location) {
        Queue<int[]> que = new LinkedList<>();
        que.offer(location);

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

            for (int i = 0; i < 12; i++) {
                int tmpX = curX + dx[i];
                int tmpY = curY + dy[i];

                if (tmpX >= 0 && tmpX < h && tmpY >= 0 && tmpY < w) {
                    if (!visited[tmpX][tmpY] && graph[tmpX][tmpY] == 1) {
                        visited[tmpX][tmpY] = true;
                        que.offer(new int[]{tmpX, tmpY});
                    }
                }
            }
        }
    }
}