[백준 1926번] - JAVA

 

• 이 문제는 입력으로 주어진 0,1중 1이 연결된 그룹의 개수와 가장 많은 1이 연결된 그룹의 1의 개수가 몇 개인지 출력하는 문제입니다.
• 0,0부터 n,m까지 확인하며 1이 연결되어 있는 부분을 찾아내면 됩니다.
• 단, 1이 연결된 부분만 찾으면 되기 때문에 탐색중 값이 0이면 굳이 탐색 로직을 수행하지 않아도 됩니다.

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

public class Main{

    private static int[] dx = {1,-1,0,0};
    private static int[] dy = {0,0,1,-1};
    private static int[][] board;
    private static boolean[][] visited;
    private static int n;
    private static int m;
    private static int cnt;
    
     public static void main(String []args) throws IOException{
        
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
        List<Integer> result = new ArrayList<>();
        
        String[] input = br.readLine().split(" ");
        
        n = Integer.parseInt(input[0]);
        m = Integer.parseInt(input[1]);
        
        board = new int[n][m];
        visited = new boolean[n][m];
        
        for(int i=0; i<n; i++)
        {
            String[] line = br.readLine().split(" ");
            for(int j=0; j<m; j++)
            {
                board[i][j] = Integer.parseInt(line[j]);   
            }
        }
        
        for(int i=0; i<n; i++)
        {
            for(int j=0; j<m; j++)
            {
                if(board[i][j] == 1 && !visited[i][j])
                {
                    cnt=1;
                    bfs(i,j);
                    result.add(cnt);
                }
            }
        }
        
        Collections.sort(result);
        int size = result.size();
        
        bw.write(Integer.toString(size)+"\n");
        
        if(size != 0)
            bw.write(Integer.toString(result.get(size-1)));
        else
            bw.write("0");
        
        br.close();
        bw.close();
     }
     
     private static void bfs(int y, int x)
     {
         Queue<int[]> q = new LinkedList<>();
         q.add(new int[]{y,x});
         visited[y][x] = true;
         
         while(!q.isEmpty()) {
             int[] cur = q.poll();
             int cy = cur[0];
             int cx = cur[1];
             
             for(int i=0; i<4; i++) {
                 int ny = cy + dy[i];
                 int nx = cx + dx[i];
                 
                 if(ny < 0 || nx < 0 || ny >= n || nx >= m) continue;
                 
                 if(visited[ny][nx] || board[ny][nx] == 0) continue;
                 
                 visited[ny][nx] = true;
                 cnt++;
                 q.add(new int[]{ny, nx});
             }
         }
     }
}

 

• main 메서드에서는 입력처리때문에 코드가 길긴하지만 중요하게 봐야할 부분은 두 번째 for문 입니다.
• 값을 하나씩 확인하여 1이 나오면 연결된 1이 있는지 찾기위해  탐색로직을 수행합니다.
• 탐색로직은 bfs메서드 입니다. 탐색을 시작하는 지점부터 0이 나올때 까지 끝까지 탐색을 하기 때문에 BFS가 적합하다고 판단하였습니다.
• 파라미터를 y와 x 순서로 두었는데, 이차원 배열의 앞부분이 행, 그 안의 값들은 열이라고 생각하여 y축, x축의 값으로 정했습니다.
• 파라미터로 받은 값을 Queue에 적재하여 탐색하는 좌표의 네 방향을 탐색하고, 1이라면 그 좌표로 이동하여 다시 탐색을 진행합니다.
• dx, dy는 네 방향 탐색을 위해 초기화해둔 값입니다.
• 1이 있다는 것은 연결되어 있다는 의미이기 때문에 cnt를 1증가해주고, 해당 좌표에 방문을 했기 때문에 visited를 true로 변경해줍니다. (main의 for문에서 재방문을 방지하기 위해)
• 이 과정을 반복하면 언젠가는 0을 만나거나 좌표값이 범위를 넘어가게 되어 종료가 되고, 이때 1로 연결된 하나의 그룹이 생성됩니다. 이 그룹의 1의 개수(=cnt)를 List에 담습니다.
• 모든 좌표의 탐색이 마무리 되었다면 List에는 1이 연결된 그룹의 1의 개수가 들어있습니다. 이를 정렬하여 가장 큰 값을 도출하면 됩니다.