백준 - 1926번 그림 (실버 1) (BFS)

대망의 bfs 첫 문제.

졸라 어렵다.

 

 

bfs 사용하는 문제

: 두 노드사이의 최단 경로를 구할 때, 임의의 경로를 구할 때 사용, flood fill 문제.

 

 

* flood fill 문제란?

: 주어진 시작점으로부터 연결된 영역들을 찾는 알고리즘 
다차원 배열의 어떤 칸과 연결된 영역을 찾는 알고리즘

 

 

구현 방법

1. 큐 생성

2. 큐에 원소 삽입, 방문여부 기록

3. 큐에서 꺼내서 상하좌우 체크
-> 큐가 빌 때까지 반복

4. 배열의 끝까지 2~3번 반복

 

*시간 복잡도는 배열의 크기만큼 걸림. O(nm)

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

class Main{
    public static class Pair{ //좌표 저장할 클래스 생성
        int x;
        int y;
        public Pair(int x,int y){
            this.x=x;
            this.y=y;
        }
    }
    public static void main(String[] args) throws IOException{
        BufferedReader br=new BufferedReader(
        new InputStreamReader(System.in));
        BufferedWriter bw=new BufferedWriter(
        new OutputStreamWriter(System.out));
        
        String[] a = br.readLine().split(" ");
        int n = Integer.parseInt(a[0]); //세로
        int m = Integer.parseInt(a[1]); //가로

        int[][] picture = new int[n][m];
        boolean[][] visited = new boolean[n][m];
        
        Queue <Pair> q=new LinkedList<>();
        
        for (int i = 0; i < n; i++) {
            String[] b = br.readLine().split(" ");
            for (int j = 0; j < m; j++) {
                picture[i][j] = Integer.parseInt(b[j]);
            }
        }
        int cnt = 0; //그림 갯수
        int max_area = 0; //제일 큰 그림의 넓이

         for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (visited[i][j] || picture[i][j] == 0) 
                    //방문했거나 값이 0이라면 다음으로
                    continue;

                cnt++; //그림 갯수 증가

                //1. 큐에 시작하는 칸을 넣고 방문표시 남기기
                q.add(new Pair(i, j));
                visited[i][j] = true;

                int current_area = 0; //현재 넓이 저장할 변수 초기화

                while (!q.isEmpty()) { //큐가 빌 때까지 반복
                    //2. 큐에서 원소를 꺼내서 그 칸에 상하좌우로 인접칸에 대해 검사
                    Pair tmp = q.remove();
                    current_area++; //꺼낼때마다 현재 넓이 증가
                    int x = tmp.x;
                    int y = tmp.y;
                    
                    if (x > 0 && !visited[x-1][y] && picture[x-1][y] == 1) { //좌
                        q.add(new Pair(x - 1, y));
                        visited[x-1][y] = true;
                    }
                    if (x < n-1 && !visited[x+1][y] && picture[x+1][y] == 1) {//우
                        q.add(new Pair(x + 1, y));
                        visited[x + 1][y] = true;
                    }
                    if (y > 0 && !visited[x][y-1] && picture[x][y-1] == 1) {//상
                        q.add(new Pair(x, y-1));
                        visited[x][y-1] = true;
                    }
                    if (y < m-1 && !visited[x][y+1] && picture[x][y+1] == 1) {//하
                        q.add(new Pair(x, y+1));
                        visited[x][y+1] = true;
                    }
                }
                if (max_area < current_area) max_area = current_area;
            }
        }
        bw.write(cnt+"\n"+max_area);
        bw.flush();
        bw.close();
    }
}