백준 1926

●문제 출처

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

●정리(요약)
어떤 큰 도화지에 그림이 그려져 있을 때, 그 그림의 개수와, 그 그림 중 넓이가 가장 넓은 것의 넓이를 출력하여라. 단, 그림이라는 것은 1로 연결된 것을 한 그림이라고 정의하자. 가로나 세로로 연결된 것은 연결이 된 것이고 대각선으로 연결이 된 것은 떨어진 그림이다. 그림의 넓이란 그림에 포함된 1의 개수이다.

첫째 줄에는 그림의 개수, 둘째 줄에는 그 중 가장 넓은 그림의 넓이를 출력하여라.

●코드 (BFS)

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 Main {
	static int [][] arr;
	static boolean [][] visited;
	static int max = 0;
	static int [] dx = {1,-1,0,0};
	static int [] dy = {0,0,1,-1};
	static int n,m;
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		n = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(st.nextToken());
		
		arr = new int[n][m];
		visited = new boolean[n][m];
		
		for(int i=0; i<n; i++) {
			st = new StringTokenizer(br.readLine());
			for(int j=0; j<m; j++) {
				arr[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		
		int count = 0;

		for(int i=0;i<n;i++){
		    for(int j=0;j<m;j++){
		        if(arr[i][j]==1 && !visited[i][j]){
		            int area = bfs(i,j);
		            count++;
		            max = Math.max(max, area);
		        }
		    }
		}
		
		System.out.println(count);
		System.out.println(max);
	}
	
	static int bfs(int y, int x){
	    Queue<int[]> q = new LinkedList<>();
	    q.add(new int[]{y,x});
	    visited[y][x] = true;

	    int area = 1;

	    while(!q.isEmpty()){
	        int[] cur = q.poll();
	        int cy = cur[0];
	        int cx = cur[1];

	        for(int i=0;i<4;i++){
	            int ny = cy + dy[i];
	            int nx = cx + dx[i];

	            if(ny>=0 && ny<n && nx>=0 && nx<m){
	                if(arr[ny][nx]==1 && !visited[ny][nx]){
	                    visited[ny][nx] = true;
	                    q.add(new int[]{ny,nx});
	                    area++;
	                }
	            }
	        }
	    }
	    return area;
	}}

●코드 (DFS)

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

public class Main {
	static int [][] arr;
	static boolean [][] visited;
	static int max = 0;
	static int [] dx = {1,-1,0,0};
	static int [] dy = {0,0,1,-1};
	static int n,m;
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		n = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(st.nextToken());
		
		arr = new int[n][m];
		visited = new boolean[n][m];
		
		for(int i=0; i<n; i++) {
			st = new StringTokenizer(br.readLine());
			for(int j=0; j<m; j++) {
				arr[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		
		int count = 0;
		for(int i =0; i<n; i++) {
			for(int j=0; j<m; j++) {
				if(arr[i][j]==1 && !visited[i][j]) {
					int area = dfs(i, j);
		            count++;
		            max = Math.max(max, area);
				}
			}
		}
		
		System.out.println(count);
		System.out.println(max);
	}
	
	private static int dfs(int y, int x) {
	    visited[y][x] = true;
	    int area = 1;

	    for (int i = 0; i < 4; i++) {
	        int ny = y + dy[i];
	        int nx = x + dx[i];

	        if (ny >= 0 && ny < n && nx >= 0 && nx < m && !visited[ny][nx] && arr[ny][nx] == 1) {
	            area += dfs(ny, nx);
	        }
	    }
	    return area;
	}
}

●느낀 점
처음에는 max의 초기값을 Integer.MIN_VALUE로 설정했는데, 제출 결과 약 50% 지점에서 오답이 발생했다. 문제를 다시 확인해 보니 그림이 하나도 없는 경우에는 가장 넓은 그림의 넓이가 0이 되어야 한다는 점을 놓치고 있었다.

또한 이 문제는 그래프 탐색 문제이기 때문에 BFS와 DFS 두 가지 방법으로 모두 구현해 보았다.
BFS는 큐를 이용해 탐색하면서 넓이를 증가시키는 방식이 직관적이었고, DFS는 재귀 호출을 통해 하나의 그림의 넓이를 누적해서 계산하는 방식으로 구현할 수 있었다.