백준 1926번 : 그림

 문제

www.acmicpc.net/problem/1926

1926번: 그림

1926 그림

 

 구현 방법

 bfs로 구현해주었습니다.

그림의 개수는 그림을 탐색할 때 1일때만 bfs를 돌게 하고 방문표시로 해당 값을 0으로 바꿔줍니다. 

그림의 넓이는 한 칸의 넓이가 1입니다. 즉, 총 칸이 몇 개 있는지를 구하고 최댓값을 구해야 하기 때문에 해당 그림을 탐색하고 Math.max 함수를 이용하여 그림의 크기가 더 큰 값을 출력해줍니다.

주의할 점은 그림이 하나도 없는 경우에는 가장 넓은 그림의 넓이는 0이므로 그림의 개수가 0일 때 0을 출력하도록 조건을 추가하였습니다.

 

 구현 코드

package BOJ.Silver.bfsdfs;

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

public class B1926_그림 {
	static int R, C, MAX, totalCnt, cnt;
	static int[][] drawing, deltas= {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
	static Queue<int[]> bfs;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		R = Integer.parseInt(st.nextToken());
		C = Integer.parseInt(st.nextToken());
		drawing = new int[R][C];
		for (int r=0;r<R;r++) {
			st = new StringTokenizer(br.readLine());
			for (int c=0;c<C;c++) {
				drawing[r][c] = Integer.parseInt(st.nextToken());
			}
		}
		bfs = new LinkedList<>();
		MAX = Integer.MIN_VALUE;
		for (int r=0;r<R;r++) {
			for (int c=0;c<C;c++) {
				if (drawing[r][c]==1) {
					drawing[r][c] = 0;
					totalCnt++; // 그림 개수
					bfs.offer(new int[] {r, c});
					bfsL();
				}
			}
		}
		
		if (totalCnt==0) System.out.println(0+"\n"+0); // 그림개수가 없을 때 최댓값은 0
		else System.out.println(totalCnt+"\n"+MAX);
	}
	
	static void bfsL() {
		cnt = 0;
		int[] now = null;
		while(!bfs.isEmpty()) {
			now = bfs.poll();
			for (int d=0;d<4;d++) {
				int nr = now[0]+deltas[d][0];
				int nc = now[1]+deltas[d][1];
				if (isIn(nr, nc) && drawing[nr][nc]==1) {
					cnt++; // 그림 크기
					drawing[nr][nc]=0; // 방문표시
					bfs.offer(new int[] {nr, nc});
				}
			}
		}
		
		MAX = Math.max(MAX, cnt+1);
	}
	
	static boolean isIn(int nr, int nc) {
		return nr>=0 && nr<R && nc>=0 && nc<C;
	}
}

 

정답!