[알고리즘]섬의 개수

4963번: 섬의 개수

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

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

package org.example.섬의개수;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.text.MessageFormat;
import java.util.LinkedList;
import java.util.Objects;
import java.util.Queue;
import java.util.StringTokenizer;

/* *
 *
 *
 *
 *
 *  */
public class Main {
    public static void main(String[] args) {
        FastReader fr = new FastReader();
        
        while (true) {
            int w = fr.nextInt();
            int h = fr.nextInt();
            if (w == 0 && h == 0) {
                break;
            }
            Area[][] areas = new Area[h][w];
            for (int x = 0; x < h; x++) {
                for (int y = 0; y < w; y++) {
                    int type = fr.nextInt();
                    areas[x][y] = new Area(w, h, x, y, type);
                }
            }
            // bfs 탐색하면서 같은 type 의 area 를 찾는다.
            // 찾은 area 는 visited 로 변경한다.
            // bfs 탐색이 끝나면 섬의 개수를 증가시킨다.
            // 모든 area 를 탐색할 때까지 반복한다.
            int count = 0;
            for (int i = 0; i < h; i++) {
                for (int j = 0; j < w; j++) {
                    Area start = areas[i][j];
                    if (start.isNotVisited() && start.isLand()) {
                        start.bfs(areas);
                        count++;
                    }
                }
            }
            System.out.println(count);
        }
    }
    
    public static class Area extends Square {
        private static final int[] dx = {0, 0, 1, -1, 1, 1, -1, -1};
        private static final int[] dy = {1, -1, 0, 0, -1, 1, 1, -1};
        
        private static final int WAY_LENGTH = dx.length;
        
        private final int x;
        private final int y;
        
        private final int type;
        
        private boolean visited;
        
        public Area(int w, int h, int x, int y, int type) {
            super(w, h);
            if (dx.length != dy.length) {
                String errorMessage = MessageFormat.format("dx, dy 의 길이는 같아야 합니다. dx: {0}, dy: {1}", dx.length, dy.length);
                throw new IllegalArgumentException(errorMessage);
            }
            if (!(0 <= x && x < h && 0 <= y && y < w)) {
                String errorMessage = MessageFormat.format("x는 0 이상  {0} 미만의 양의 정수 y는 0이상 {1} 미만의 양의 정수여야합니다. . x: {2}, y: {3}", h, w, x, y);
                throw new IllegalArgumentException(errorMessage);
            }
            if (!(0 <= type && type <= 1)) {
                String errorMessage = MessageFormat.format("type은 0 또는 1이어야 합니다. type: {0}", type);
                throw new IllegalArgumentException(errorMessage);
            }
            this.x = x;
            this.y = y;
            this.type = type;
        }
        
        public boolean bfs(Area[][] areas) {
            Objects.requireNonNull(areas, "areas 는 null 일 수 없습니다.");
            Queue<Area> queue = new LinkedList<>();
            queue.add(this);
            this.visited = true;
            
            while (!queue.isEmpty()) {
                Area current = queue.poll();
                for (int i = 0; i < WAY_LENGTH; i++) {
                    int nx = current.x + dx[i];
                    int ny = current.y + dy[i];
                    if (!(0 <= nx && nx < h && 0 <= ny && ny < w)) {
                        continue;
                    }
                    Area next = areas[nx][ny];
                    if (next.isLand() && next.isNotVisited()) {
                        next.visited = true;
                        queue.add(areas[nx][ny]);
                    }
                }
            }
            return true;
        }
        
        private boolean isNotVisited() {
            return !this.visited;
        }
        
        private boolean isLand() {
            return this.type == 1;
        }
        
        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (!(o instanceof Area)) return false;
            
            Area area = (Area) o;
            
            if (x != area.x) return false;
            if (y != area.y) return false;
            if (type != area.type) return false;
            return visited == area.visited;
        }
        
        @Override
        public int hashCode() {
            int result = x;
            result = 31 * result + y;
            result = 31 * result + type;
            result = 31 * result + (visited ? 1 : 0);
            return result;
        }
    }
    
    public static class Square {
        protected final int w;
        protected final int h;
        
        public Square(int w, int h) {
            if (!(1 <= w && w <= 50 && 1 <= h && h <= 50)) {
                String errorMessage = MessageFormat.format("w, h 는 1 이상 50 이하의 정수여야 합니다. w: {0}, h: {1}", w, h);
                throw new IllegalArgumentException(errorMessage);
            }
            this.w = w;
            this.h = h;
        }
        
    }
    
    public static class FastReader {
        
        BufferedReader br;
        StringTokenizer st;
        
        public FastReader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }
        
        public String next() {
            while (Objects.isNull(st) || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return st.nextToken();
        }
        
        public int nextInt() {
            return Integer.parseInt(next());
        }
        
    }
}

Uploaded by N2T