백준 1926 - 그림

Java

1926 번 - 그림

문제

접근 방법

0,0부터 n-1, m-1 까지 탐색을 하여, 만약 1을 발견하면 그 위치부터 BFS로 근처의 인접한 모든 1을 탐색한다.
탐색한 1의 개수를 세고 1을 0으로 바꾸어 방문 여부를 표기한다.

구한 가장 넓은 그림의 넓이를 구하고, BFS를 호출 할 때마다 그림 수가 늘어나는 것이므로, 호출 개수를 세어 그림의 수를 구한다.

코드

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

public class Main {
	static int n, m, largest, drawingCnt;
	static int[][] map;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer stk = new StringTokenizer(br.readLine());
    	n = stoi(stk.nextToken());
    	m = stoi(stk.nextToken());

    	map = new int[n][m];

    	for(int i = 0; i < n; i++) {
    		stk = new StringTokenizer(br.readLine());
    		for(int j = 0; j < m; j++) {
    			map[i][j] = stoi(stk.nextToken());
    		}
    	}

    	for(int i = 0; i < n; i++) {
    		for(int j = 0; j < m; j++) {
    			if(map[i][j] == 1) {
    				largest = Math.max(largest, BFS(i,j));
    				drawingCnt++;
    			}
    		}
    	}

    	System.out.println(drawingCnt);
    	System.out.println(largest);

    	br.close();
	}

    static int dy[] = {-1,1,0,0};
	static int dx[] = {0,0,-1,1};

	 // 주어진 범위 안에 있는가
    public static boolean isIn(int y, int x){
        if(y < 0 || y >= n || x < 0 || x >= m)
            return false;
        return true;
    }

	public static int BFS(int y, int x) {
		int count = 1;
		Queue<int[]> queue = new LinkedList<int[]>();
		queue.add(new int[] {y,x});

		map[y][x] = 0;

		int[] q;
		int ny,nx;

		while(!queue.isEmpty()) {
			q = queue.poll();
			y = q[0];
			x = q[1];
			for(int i = 0; i < 4; i++) {
				ny = y + dy[i];
				nx = x + dx[i];
				if(isIn(ny,nx) && map[ny][nx] == 1) {
					queue.add(new int[] {ny,nx});
					count++;
					map[ny][nx] = 0;
				}
			}
		}

		return count;
	}

	static int stoi(String str) {
    	return Integer.parseInt(str);
    }
}

총평

후기

개선할 점