백준 1926 그림 (Java)

1. 문제 링크

1926번: 그림

 

2. 문제 및 입출력예제

 

3. 문제 풀이

처음에는 우, 하만 확인하면 될거라고 생각했는데

역시 아니었고….

아래의 반례에서 틀렸다. (dfs로 돌아가니까 사방으로 탐색하는게 맞지..)

4 5

1 1 1 0 1

1 0 1 0 1

1 0 1 0 1

1 0 1 1 1

 

dfs탐색을 사방으로 하면서 각 그림의 크기를 list에 추가했다.

전체를 돌고 나서는 list를 정렬하여 그림의 개수와 그림의 최대 크기를 출력했다.

 

4. 코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Queue;
import java.io.IOException;

public class Main {
	static int N, M, cnt, max;
	static boolean[][] map, visit;
	static int[] dx = {0,0,-1,1}, dy = {-1,1,0,0};
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] split = br.readLine().split(" ");
		N = Integer.parseInt(split[0]);
		M = Integer.parseInt(split[1]);
		map = new boolean[N][M];
		visit = new boolean[N][M];
		for(int i=0;i<N;i++) {
			split = br.readLine().split(" ");
			for(int j=0;j<M;j++) {
				if(split[j].equals("0")) {
					map[i][j] = false;
				}
				else {
					map[i][j] = true;
				}
			}
		} //입력 끝
		
		ArrayList<Integer> list = new ArrayList<>();
		for(int i=0;i<N;i++) {
			for(int j=0;j<M;j++) {
				if(map[i][j] && !visit[i][j]) {
					cnt = 0;
					dfs(i, j);
					list.add(cnt);
				}
			}
		}		
		Collections.sort(list);
		int size = list.size();
		if(size==0) {
			System.out.println(0+"\n"+0);
		}
		else {
			System.out.println(size+"\n"+list.get(size-1));
		}
	}
	private static void dfs(int x, int y) {
		visit[x][y] = true;
		cnt++; 
		for(int d=0;d<4;d++) {
			int X = x+dx[d];
			int Y = y+dy[d];
			if(X>=0 && X<N && Y>=0 && Y<M && !visit[X][Y] && map[X][Y]) {
				dfs(X, Y);
			}
		}
	}
}