백준 1926 그림 자바

문제는 다음과 같다.
https://www.acmicpc.net/problem/1926

코드는 다음과 같다.

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

public class Main {
    static int[] dr = {-1, 1, 0, 0}; //상, 하, 좌, 우 순서
    static int[] dc = {0, 0, -1, 1};
    static int[][] map;
    static boolean[][] visited;
    static int R, C;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st1 = new StringTokenizer(br.readLine());
        R = Integer.parseInt(st1.nextToken());
        C = Integer.parseInt(st1.nextToken());
        map = new int[R][C];
        visited = new boolean[R][C];
        
        for(int r = 0 ; r < R ; r++) { //map 채우기
            StringTokenizer st2 = new StringTokenizer(br.readLine());
            for(int c = 0 ; c < C ; c++) {
                map[r][c] = Integer.parseInt(st2.nextToken());
            }
        }
        
        //초깃값 세팅
        int max = 0; //뭉탱이의 최댓값
        int answer = 0; //몇개의 뭉탱이를 돌았는지

        for(int r = 0 ; r < R ; r++) {
            for(int c = 0 ; c < C ;c++) {

                if(visited[r][c] == false && map[r][c] == 1) { //r, c 방문 안했고, map 값이 1이라면


                    int a = BFS(r, c); //BFS 실행시켜서 뭉탱이 돌면서 + 뭉탱이 몇개 돌았는지 return
                    if(max < a) { //돌면서 뭉탱이 안에 몇개있는지 최댓값 갱신
                        max = a;
                    }
                    answer++; //뭉탱이 돌아서 answer ++ 해주기.
                }

            }
        }

        bw.write(String.valueOf(answer) + "\n");
        bw.write(String.valueOf(max));
        bw.flush();
        bw.close();

    }
    
    static int BFS(int r, int c) { //BFS 두가지 역할 수행. 통과한 행렬 체크 + 몇개 통과했는지 리턴(max 값 뽑기)
        Queue<int[]> q = new LinkedList<>();
        int how_many = 0;
        q.add(new int[] {r, c});

        while(!q.isEmpty()) {
            int[] now = q.poll();
            how_many++;
            visited[now[0]][now[1]] = true;


            for(int i = 0 ; i < 4 ; i++) {
                int next_r = now[0] + dr[i];
                int next_c = now[1] + dc[i];

                if(next_r >= 0 && next_c >= 0 && next_r < R && next_c < C && //index 만족하고
                        visited[next_r][next_c] == false && map[next_r][next_c] == 1) { //방문 안했고 값이 1이라면
                       q.add(new int[] {next_r, next_c});
                       visited[next_r][next_c] = true;

                }
            }

        }

        //여기까지 오면 BFS 끝, 몇개돌았는지 return
        return how_many;
    }

}

원래 BFS를 알고있다면, 이해는 쉽다.
내가 해준건,
map을
문제에서 준 조건대로 map[r][c] 값이 1이라면
BFS로 순회하면서
how_many로 몇개를 순회했는지 개수를 세주고,
순회하는 친구들을 visited[r][c] = true로 체크하면서
한번 돌았으면 다시 돌지 못하도록 했다.

예를 들어
111
000
000
의 map을 BFS를 돌면,
1행 1열을 먼저 들어가게 되고,
1행의 뭉탱이 111을 돌게 되며
BFS 매서드의 로직에 의해 how_many는 3이 될거고 (세 개를 돌았으니)
visited[0][0], visited[0][1], visited[0][2]
는 true가 될거다.
해당 visited 행렬이 true가 되니까,

 if(visited[r][c] == false && map[r][c] == 1)

이 로직에 의해 한번 돈 뭉탱이의 내용물들은 다시 돌지 않도록 해주었다.


이렇게 작동하도록 BFS 매서드를 만들었다.
이정도가 이해간다면 더 자세한 내용은 코드를 보며
주석을 보며 읽어내려가면 충분히 이해 갈 것 같다.