Map이 주어지고, 탐색을 통해서 넓이나 길을 찾는 문제 유형.

백준 Q1926

Sample Source Code


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

public class Main {

	public static void main(String[] args) {
		
		try {
			// 입력 처리
			BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
			StringTokenizer st = new StringTokenizer(br.readLine());
			
			int R 	= Integer.parseInt(st.nextToken());
			int C 	= Integer.parseInt(st.nextToken());
			
			int[][] map	= new int[R+1][C+1];
			int[][] ck	= new int[R+1][C+1];
			
			for(int i=1;i<=R;i++) {
				st = new StringTokenizer(br.readLine());
				for(int j=1;j<=C;j++) {
					map[i][j] = Integer.parseInt(st.nextToken());
				}
			}
			
			int[] dx = new int[] {1,0,-1,0};
			int[] dy = new int[] {0,1,0,-1};
			
			
			int max_zone 	= 0;//영역의 갯수
			int max_count	= 0;//최대 영역의 수
			
			Queue<int[]> q = new LinkedList();
			
			
			for(int i=1;i<=R;i++) {
				for(int j=1;j<=C;j++) {
					
					int temp_count = 0;
					
					if( map[i][j]==1 && ck[i][j]==0){
						ck[i][j] = 1;
						q.add(new int[] {i,j}); // 행, 열
						max_zone++;
						temp_count++;
					}//end if
					
					while(! q.isEmpty() ) {
						int[] cur  	= q.poll();
						int r 		= cur[0];
						int c 		= cur[1];
						
						//현재 방문 처리
						//ck[r][c] 	= 1;
						
						for(int k=0; k < 4;k++) {
							int new_r = r + dy[k];
							int new_c = c + dx[k];
							
							if( new_c > C || new_c < 1 || new_r > R || new_r < 1) continue;
							
							//System.out.format("%d, %d\n",new_c,new_r);
							
							if( map[new_r][new_c] ==1 && ck[new_r][new_c] == 0 ){ //ck[행][열]
								ck[new_r][new_c] = 1;
								q.add(new int[] {new_r,new_c});
								temp_count++;
							}
						}
						
						max_count	= Math.max(max_count, temp_count);
					}//while
					
					
				}//end for
			}//end for
			
			
			System.out.println(max_zone);
			System.out.println(max_count);
			
			
		}catch(Exception e) {
			e.printStackTrace();
		}
	
	
	}
}
/*
입력
6 5
1 1 0 1 1
0 1 1 0 0
0 0 0 0 0
1 0 1 1 1
0 0 1 1 1
0 0 1 1 1

출력
4
9

*/

참고