문제 탐색하기

입력 자료 정리하기

1. N은 지도의 가로 세로 길이다
2. 이후 들어오는 입력값들은 지도의 각 좌표 위치에 해당하는 값들을 의미한다.
3. 이때 1은 탐색해야되는 값이며, 0은 탐색할 필요가 없는 값이다.

해결방법 추론

1. 이번 문제도 좌표 평면 문제다. 일단 크기 n이 최대 25이므로 dp는 필요 없다.
2. 이어서 상하좌우 탐색을 하면서, 붙어있는 1의 개수를 세어줘야하므로 BFS 탐색을 생각하였다
3. 이렇게 붙어있는 1의 뭉탱이를 하나의 단지라고 한다.
   이때 단지가 한가지가 아니며 여러가지이므로 브루트 포스를 하면서,
   모든 단지에 대한 bfs 탐색을 해야한다
4. 따라서 브루트포스 + BFS 탐색을 통해 해당 문제를 해결할 수 있다.

시간복잡도 계산

1. 시간복잡도는 얼마가 발생할지 알아보자. 먼저 브루트포스에서 n x n만큼의 연산이 발생한다
2. 그리고 각 bfs마다 4방 탐색이므로 4의 연산이 발생한다
3. 따라서 총 발생하는 연산은 n x n x 4이므로 시간복잡도는 O(n^2 x 2)가 된다
4. n의 최댓값은 25이므로 시간제한인 1초안에 해당 방법으로 해결할 수 있다

코드 설계하기

입력값 상태 관리하기

1. 입력값들에 대해서 크기 n은 변수로 관리한다
2. 각 좌표의 값들은 int형 2차원 배열로 관리한다

탐색전 설계

1. BFS 탐색을 위한 방문 배열과 상하좌우 탐색을 편리하게 해줄 dx,dy배열을 각각 선언한다
2. 앞서 설계했듯이 이 문제에서는 정답이 되는 단지가 여러가지가 될 수 있다
3. 따라서 해당 값을 관리할 정답 리스트를 하나 만들어준다

브루트포스 설계

1. 브루트포스로 모든 위치를 확인하면서 현재 위치의 값이 1이고 미방문했으면 bfs 탐색을 한다
2. 이번 bfs도 반환값을 갖도록 설계하는데, 앞서 설계한 정답을 관리할 리스트에 반환값을 넣어준다

BFS 탐색 설계

1. 이번에는 누적되는 거리값 없이 y,x값만 큐에 넣고 탐색한다
2. 단지의 개수를 세어줘야 하므로, count 변수를 하나 선언한다
3. 이때 BFS 탐색을 하기 위해서는 처음값이 무조건 존재해야하므로, count는 1로 초기화한다
4. BFS 탐색을 진행하면서 4방 탐색을한다.
5. 이때 인덱스 범위를 벗어나지 않고,
   미방문했으며 해당 위치가 1이라면 방문체크와 큐에 넣는 작업을 한다
6. 또한 앞서 선언한 count의 개수도 증가시킨다
7. 이렇게 BFS 탐색을 통해 완성한 count를 반환값으로 넘겨준다

출력 설계

1. 받은 정답값들을 보관하는 리스트를 오름차순으로 출력하기 위해 오름차순 정렬을 해준다
2. 리스트의 크기를 먼저 출력하고, for-each로 리스트의 모든 정답값들을 출력하면 정답이 된다.

정답코드

(1회차 시도 성공!)

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



public class Main {


    static int[][] arr;
    static boolean[][] visited;
    static int[] dy = {-1,1,0,0};
    static int[] dx = {0,0,-1,1};
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int n = Integer.parseInt(br.readLine());
        arr = new int[n][n];
        for (int i = 0; i < n; i++) {
            char[] s = br.readLine().toCharArray();
            for (int j = 0; j < n; j++) {
                arr[i][j] = Character.getNumericValue(s[j]);
            }
        }
        List<Integer> ans = new ArrayList<>();
        visited = new boolean[n][n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if(arr[i][j] == 1 && !visited[i][j]){
                    ans.add(bfs(n, i,j));
                }
            }
        }

        Collections.sort(ans);
        bw.write(ans.size()+"\n");
        for (Integer an : ans) {
            bw.write(an+"\n");
        }

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

    private static Integer bfs(int n, int y, int x) {
        Queue<int[]> q = new LinkedList<>();

        q.add(new int[]{y,x});
        visited[y][x] = true;
        int count = 1;
        while(!q.isEmpty()){
            int[] now = q.poll();
            for (int i = 0; i < 4; i++) {
                int ny = dy[i] + now[0];
                int nx = dx[i] + now[1];
                if(ny >=0 && ny < n && nx >=0 && nx < n && !visited[ny][nx] && arr[ny][nx] == 1){
                    visited[ny][nx] = true;
                    q.add(new int[]{ny, nx});
                    count++;
                }
            }

        }
        return count;
    }
}

문제 링크

2667번 - 단지번호붙이기