알고리즘
BOJ 1926 - 그림
Llife
2020. 8. 31. 22:36
1926번: 그림
어떤 큰 도화지에 그림이 그려져 있을 때, 그 그림의 개수와, 그 그림 중 넓이가 가장 넓은 것의 넓이를 출력하여라. 단, 그림이라는 것은 1로 연결된 것을 한 그림이라고 정의하자. 가로나 세로��
www.acmicpc.net
BFS 문제 풀어봤습니다.
힘들어!
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
public class boj1926 {
static int[][] arr;
static boolean[][] visited;
static int[] dx = {-1,1,0,0};
static int[] dy = {0,0,-1,1};
static int max = 0;
static int picutre = 0;
static int R;
static int C;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
R = sc.nextInt();
C = sc.nextInt();
arr = new int[R][C];
visited = new boolean[R][C];
for(int i=0; i<R; i++){
for(int j=0; j<C; j++){
arr[i][j] = sc.nextInt();
}
}
for(int i=0; i<R; i++){
for(int j=0; j<C; j++){
if(visited[i][j] == false && arr[i][j] == 1) {
visited[i][j] = true;
Pair pair = new Pair(i,j);
BFS(pair);
picutre++;
}
}
}
System.out.println(picutre);
System.out.println(max);
}
private static void BFS(Pair pair) {
Queue<Pair> queue = new LinkedList<>();
queue.add(pair);
int area = 1;
while (!queue.isEmpty()){
Pair cur = queue.poll();
// System.out.println("CUR X " + cur.x + " CUR Y " + cur.y);
for(int dir=0; dir<4; dir++){
int nx = cur.x + dx[dir];
int ny = cur.y + dy[dir];
if(nx <0 || nx >= R || ny<0 || ny >= C) continue;
if(visited[nx][ny] == true || arr[nx][ny] == 0) continue;
visited[nx][ny] = true;
queue.add(new Pair(nx,ny));
area++;
}
}
max = Math.max(area, max);
}
static class Pair{
int x;
int y;
Pair(int x, int y){
this.x = x;
this.y = y;
}
}
}