[백준] 1926번 - 그림 (Java)

https://www.acmicpc.net/problem/1926

1926번: 그림

 

<문제 분석>

map : 1과 0으로 구성. 
그림 : 상하좌우가 1로 연결된 것

그림의 갯수와 가장 큰 그림의 넓이를 출력한다.
그림이 하나도 없는 경우에는 가장 큰 그림의 넓이는 0을 출력한다.

입력정보
세로축 N : <= 500
가로축 M : <= 500

<풀이>
1. map에서 탐색을 통한 그룹화 문제이므로 FloodFill 알고리즘을 사용한다.
2. 이중 for문을 돌려서 1이 나오면 FloodFill(x, y)를 호출한다.
  - 이미 방문한 위치면 스킵한다.
  - map[x][y]가 0이면 스킵한다.
  - 그룹번호를 FloodFill()를 호출할 때마다 전달한다.
3. FloodFill(int x, int y) 구현
  - 큐에 전달받은 위치(x, y)를 삽입한다.(필요시 class 구성)
  - 방문처리 한다. visited[x][y] = true
  - 큐가 빌때까지 반복한다.
  - 상하좌우로 탐색한다.
  - map 범위를 벗어나거나, 이미 방문한 곳이거나, 0이면 스킵한다.
  - 방문처리하고 map은 그룹번호를 더해서 그룹화를 한다.
  - 큐에 새 위치를 삽입한다.
  - 큐에 삽입할 때 누적거리를 별도의 변수에 저장한다.
  - FloodFill 탐색이 종료되면 기존 넓이와 지금 넓이를 비교해서 최대값을 업데이트 한다.

(설계 완료 : 23분)
(코드 구현 : 45분)

 

<코드 구현>

import java.util.Scanner;
import java.util.Queue;
import java.util.LinkedList;
import java.lang.Math;


//[백준] [백준] 1926번 - 그림 (Java)

public class Main {
    static int N, M;
    static boolean visited[][];
    static int map[][];

    class Point {
        int x, y;
        Point (int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
    
    public void InputData() {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        M = sc.nextInt();
        map = new int[N][M];
        for (int i=0; i<N; i++) {
            for (int j=0; j<M; j++) {
                map[i][j] = sc.nextInt();
            }
        }
    }

    static int dx[] = {-1, 0, 1, 0};
    static int dy[] = {0, 1, 0, -1};
    static int max_len = Integer.MIN_VALUE;
    public void FloodFill(int x, int y) {
        Queue<Point> Q = new LinkedList<>();
        // FloodFill 시작점 처리
        Q.add(new Point(x, y));
        visited[x][y] = true;
        int next_len = 1; // 넓이니까 1부터 시작
        while(!Q.isEmpty()) {
            Point now = Q.poll();
            for (int i=0; i<4; i++) {
                int nx = now.x + dx[i];
                int ny = now.y + dy[i];
                if (nx < 0 || nx >= N || ny < 0 || ny >= M) continue;
                if (map[nx][ny] == 0) continue;
                if (visited[nx][ny]) continue;
                visited[nx][ny] = true;
                next_len++;
                Q.add(new Point(nx, ny));
            }
        }
        max_len = Math.max(max_len, next_len); // 현 그림의 최종 넓이외 기존 넓이 비교
    }


	public void Solve() {
        visited = new boolean[N][M];
        int paint_num = 0;
        for (int i=0; i<N; i++) {
            for (int j=0; j<M; j++) {
                if (map[i][j] == 0) continue;
                if (visited[i][j]) continue;
                FloodFill(i, j);
                paint_num++; // 그림번호 증가
            }
        }
        System.out.println(paint_num);
        System.out.println(paint_num == 0 ? 0:max_len); // 그림이 없으면 0출력
	}
    
	public static void main(String[] args)
	{
		Main m = new Main();
		m.InputData();///입력
		//코드를 작성하세요
        m.Solve();
	}
}

 

<제출 결과>