BOJ) 섬의 개수

섬의 개수

4963번: 섬의 개수

풀이

 

섬의 개수를 찾는 문제로, 인접한 8구역이 땅이면 이동할 수 있다는 조건을 가지고 있다.

제약 조건이 기존 4곳에서 대각선들만 추가됐을뿐, 일반적인 grouping 문제다.

grouping 문제는 이전 문제들에서 많이 다뤘기 때문에 큰 풀이는 남기지 않으려고 한다.

다만, 좌 우의 상/하 대각선을 예외처리 없이 검사하기 위해 map의 크기를 입력받은 n,m값 +2로 설정해줬다는 점이 특이하다 정도는 주의할만 하다.

그리고, 한 메소드 당 하나의 기능만 하도록 분리하려 했다는 점과 여는 괄호( { )의 깊이가 깊어지지 않도록 했다는 점도 주목할만 했다.

 

코드

 

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

public class Main {
    final static String END = "0 0", NEWLINE = "\n";
    final static int LAND = 1;
    final static int[] dx = {0,1,1,1,0,-1,-1,-1}, dy = {-1,-1,0,1,1,1,0,-1};

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String inputStr = "";
        StringTokenizer st;
        StringBuffer sb = new StringBuffer();

        while( !(inputStr = br.readLine()).equals(END)) {
            st = new StringTokenizer(inputStr);
            int w = Integer.parseInt(st.nextToken()), h = Integer.parseInt(st.nextToken());
            int[][] map = new int[h+2][w+2];
            for(int y=1; y<=h; y++) {
                st = new StringTokenizer(br.readLine());
                for(int x=1; x<=w; x++)	map[y][x] = Integer.parseInt(st.nextToken());
            }
            sb.append(getIslands(w,h,map)).append(NEWLINE);
        }
        System.out.println(sb.toString());
    }

    private static int getIslands(int w, int h, int[][] map) {  // 0 : 땅, -1 : 물
        int groupID =1;
        for(int y=1; y<=h; y++) {
            for(int x=1; x<=w; x++) {
                if(map[y][x] ==LAND) {
                    map[y][x] = ++groupID;
                    map = grouping(new Pos(x,y),map, groupID);
                }
            }
        }
        return groupID-1;
    }

    private static int[][] grouping(Pos start, int[][] map, int groupID) {
        LinkedList<Pos> moveList = new LinkedList<>();
        moveList.offer(start);
        while(!moveList.isEmpty()) {
            Pos pos = moveList.poll();
            for(int i=0; i<8; i++) {
                int nx = pos.x+dx[i], ny = pos.y+dy[i];
                if(map[ny][nx] == LAND) {
                    map[ny][nx] = groupID;
                    moveList.offer(new Pos(nx,ny));
                }
            }
        }
        return map;
    }

    private static class Pos {
        int x,y;
        public Pos(int x, int y) {
            this.x=x;
            this.y=y;
        }
    }
}