[JAVA65] 4963. 섬의개수

4963. 섬의개수 (S2)

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
1 초	128 MB	74810	38186	27381	49.865 %

 

문제

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

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

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

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다.

둘째 줄부터 h개 줄에는 지도가 주어진다. 1은 땅, 0은 바다이다.

입력의 마지막 줄에는 0이 두 개 주어진다.

출력

각 테스트 케이스에 대해서, 섬의 개수를 출력한다.

---

summary

섬의 개수 구하기

• 가로세로대각선으로 인접해있으면 하나의 섬임
• 땅 크기가 0 0 으로 입력들어오기 전까지 반복함
• 땅 크기는 w h 로 입력

strategy

완전 탐색 (BFS) 활용

• 땅 정보를 입력받을 때 땅에 해당하는 부분 따로 저장 (Queue lands)
• 땅에 해당하는 좌표를 순회하면서 섬 크기 계산
• 시작 땅이 이미 방문한 적 있으면 패스 (visited)
• 시작 땅을 기준으로 순회 
• 땅 순회 할 때 큐에 좌표 저장 (Queue q)
• 범위 벗어나는지, 방문한 적있는지, 땅인지 체크한 후 큐에 저장

note

• w와 h는 50

import java.util.*;
import java.io.*;
import java.awt.Point;

public class Main {
    static int N, M;
    static boolean[][] board, visited;
    static int[][] dir = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}, {1, 1}, {1, -1}, {-1, 1}, {-1, -1}}; // 이동방향
    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder answer = new StringBuilder();
        
        while(true) {
            StringTokenizer input = new StringTokenizer(br.readLine());

            M = Integer.parseInt(input.nextToken());
            N = Integer.parseInt(input.nextToken());

            if(N == 0 || M == 0) break; // 종료 조건

            // 좌표 입력
            board = new boolean[N][M];
            visited = new boolean[N][M];

            Queue<Point> lands = new ArrayDeque<>();
            for(int n = 0; n < N; n++) {
                input = new StringTokenizer(br.readLine());
                for(int m = 0; m < M; m++) {
                    board[n][m] = (input.nextToken().equals("1") ? true : false); // 땅(1) 이면 true, 바다(0) 이면 false

                    if(board[n][m]) lands.add(new Point(n, m));
                }
            }

            // 섬 순회
            int cnt = 0;
            while(!lands.isEmpty()) {
                Point startLand = lands.poll();

                if(visited[startLand.x][startLand.y]) continue; // 이미 방문

                BFS(startLand);
                cnt++;
            }

            answer.append(cnt).append("\n");
        }

        System.out.println(answer);
        br.close();
    }

    private static void BFS(Point startLand) {
        Queue<Point> q = new ArrayDeque<>();
        q.add(startLand);
        visited[startLand.x][startLand.y] = true; // 방문 처리

        while(!q.isEmpty()) {
            Point currentLand = q.poll();

            for(int[] d : dir) {
                int mx = currentLand.x + d[0];
                int my = currentLand.y + d[1];

                if(mx < 0 || my < 0 || mx >= N || my >= M) continue; // 범위 벗어남
                if(visited[mx][my]) continue; // 이미 방문
                if(!board[mx][my]) continue; // 바다

                visited[mx][my] = true; // 방문처리
                q.add(new Point(mx, my));
            }
        }
    }
}

문제	결과	메모리	시간	언어코드	길이
4963	맞았습니다!!	16900 KB	144ms	Java 11 / 수정	2391B

memo

• 땅 크기가 당연히 h w 크기로 주어지는 줄 알고 계속 실수