문제 탐색하기

입력 자료 정리

1. 처음 들어오는 두 값은 각각 가로 길이와 세로길이다.
2. 가로줄 세로줄이 아닌 길이이므로 이후 배열 선언할때, 뒤집어서 크기를 초기화해야한다
3. 이후 들어오는 h x w 만큼의 입력은 각 인덱스의 원소값이다.
4. 들어오는 원소값은 1과 0으로 고정된다. 이때 1은 땅이고 0은 물로, 1이 탐색의 대상이된다

해결방법 추론

1. 문제를 보자마자 이건 BFS로 풀면 되겠다고 생각하였다
2. 모든 지점을 탐색하면서, 땅이 있는 부분의 개수를 세어주면 된다
3. 이때, 서로 연결되어 있는 땅이면서 한번도 방문하지 않은 땅이라면 하나의 섬이라는 의미이고,
   연결된 땅 전체를 하나로 봐야하기 때문에 여기서 BFS 탐색을 활용하면 된다
4. BFS와 방문체크를 활용한다면, 모든 섬의 개수를 손쉽게 계산할 수 있을 것이다

시간복잡도 계산

1. 모든 땅을 탐색하는 과정에서 h x w만큼의 연산이 발생한다
2. 이어서 BFS에서도 추가적인 연산이 발생할 수 있는데,
   땅이 연결되어 있는 경우 그 연결된 땅을 이어서 탐색하기 때문이다
3. 하지만 BFS 탐색이 전체 탐색에 영향을 주지 않는다.
   왜냐하면 방문 체크로 한번 방문한 땅은 재방문하지 않기 때문이다.
4. 따라서 전체 연산은 h x w만큼 발생하고 시간복잡도는 O(h x w)가 된다
5. h와 w의 최대 연산은 50 x 50으로 시간제한을 넘지 않으며,
   테스트 케이스도 그 최대 연산을 주지 않았으므로 시간제한에 걸리지 않는 양을 주었을 것이므로
   시간초과없이 문제를 해결할 수 있다

코드 설계하기

입력값 상태 관리

1. 주어지는 입력이 조금 깨끗하지 않지만, 많이 해봤기에 익숙하게 관리할 수 있다
2. while(true)문에서 테스트케이스를 반복해서 받는데,
   변수로 받은 w와 h가 둘다 0일 경우에는 break로 탈출해서 입력을 종료시킨다
3. 이어서 들어오는 값들은 int형 타입의 2차원 배열에 저장한다.
   이때 이 배열의 크기는 h x w이다.
4. 방문체크를 위한 배열도 똑같은 크기로 만들어둔다

BFS 탐색 설계

1. 탐색 전 정답 출력을 위한 count 변수를 0으로 초기화해둔다
2. 이어서 h x w만큼 탐색하면 현재 위치의 인덱스 값이 미방문이고 1인 경우,
   bfs탐색을 시작한다. 또한 이어서 섬을 발견한 것이므로 count의 개수도 증가시킨다
3. 탐색을 위한 큐를 하나 선언한다.
   y, x 두 좌표를 관리해야하므로 int형 타입으로 큐를 선언한다
4. 탐색 시작 지점을 큐에넣고 방문 체크한 뒤, BFS 탐색을 시작한다
5. 이 문제에서는 8방 탐색을 해야한다.
   미리 만들어둔 8방 탐색 배열을 활용하며, 인덱스 범위를 벗어나지 않고 미방문했으면서
   원소가 1인 지점 즉, 땅인 지점만을 탐색의 대상으로 한다
6. 5번 조건에 해당하면 방문체크 후, 해당 좌표를 큐에 넣어준다

출력 설계

1. 이렇게 BFS 탐색와 브루트포스로 모든 지점을 탐색한 결과
   완성된 count를 출력하면 정답이 된다.

정답 코드

(1회차 시도 성공!)

import java.io.*;
import java.util.*;


public class Main {

    static int[] dx = {-1,0,1,-1,1,-1,0,1};
    static int[] dy = {-1,-1,-1,0,0,1,1,1};
    static int[][] arr;
    static boolean[][] visited;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        while(true){
            StringTokenizer st = new StringTokenizer(br.readLine());
            int w = Integer.parseInt(st.nextToken());
            int h = Integer.parseInt(st.nextToken());
            if(w == 0 && h == 0){
                break;
            }
            arr = new int[h][w];
            visited = new boolean[h][w];
            for (int i = 0; i < h; i++) {
                st = new StringTokenizer(br.readLine());
                for (int j = 0; j < w; j++) {
                    arr[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] && arr[i][j] == 1){
                        bfs(i,j,w,h);
                        count++;
                    }
                }
            }


            bw.write(count+"\n");

        }


        br.close();
        bw.close();
    }

    private static void bfs(int y, int x, int w, int h) {
        Queue<int[]> q = new LinkedList<>();
        q.add(new int[]{y,x});
        visited[y][x] = true;
        while(!q.isEmpty()){
            int[] now = q.poll();
            for (int i = 0; i < 8; i++) {
                int ny = now[0] + dy[i];
                int nx = now[1] + dx[i];
                if(ny >= 0 && ny < h && nx >= 0 && nx < w && !visited[ny][nx] && arr[ny][nx] == 1){
                    visited[ny][nx] = true;
                    q.add(new int[]{ny,nx});
                }
            }

        }

    }

}

문제 링크

4963번 - 섬의 개수