BOJ_1926 : 그림

👉 문제링크

1926번: 그림

---

---

🔸 문제 분석 🔸

• n * m 도화지에서 연결된 1의 개수의 최대값을 출력한다.
  • BFS혹은 DFS로 연결된 1을 탐색한다.
  • 연결된 1 무리의 개수와 그 중 최대값을 출력한다.

🔸 코드 🔸

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        // input
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());

        boolean[][] arr = new boolean[n][m];

        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < m; j++) {
                arr[i][j] = Integer.parseInt(st.nextToken()) != 0;
            }
        }

        // bfs
        int cnt = 0, max = 0;
        int[] dx = {-1, 0, 1, 0};
        int[] dy = {0, 1, 0, -1};

        Queue<Pair> que = null;

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (arr[i][j]) {
                    int temp = 0;
                    cnt++;
                    que = new ArrayDeque<>();
                    que.add(new Pair(i,j));
                    arr[i][j] = false;

                    while (!que.isEmpty()) {
                        temp++;
                        Pair pair = que.poll();
                        for (int k = 0; k < 4; k++) {
                            int r = pair.r+dx[k];
                            int c = pair.c+dy[k];

                            if (0<=r&&r<n && 0<=c && c<m&&arr[r][c]){
                                arr[r][c] = false;
                                que.offer(new Pair(r,c));
                            }
                        }
                    }
                    max = Math.max(max, temp);
                }
            }
        }
        System.out.println(cnt);
        System.out.println(max);
    }

    private static class Pair{
        int r, c;

        public Pair(int r, int c) {
            this.r = r;
            this.c = c;
        }
    }
}

🔸 코드 해석 🔸

• n * m 크기의 2차원 배열 arr를 탐색하며 true를 찾는다.
  • 발견한 좌표를 큐에 넣고 BFS로 인접한 1을 모두 false로 바꾼다.
  • 이때 무리의 수 cnt를 +1해주고, 인접한 1의 개수를 따로 카운트해서 max를 업데이트한다.

---

🔸 end 🔸

• 기본적인 그래프 탐색 문제여서 무리없이 풀었던 것 같다.