백준 2667 단지 번호 붙이기

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

dfs의 기본이 되는문제

dfs 기초 유형을 익히기 좋은문제이다

메인로직

1. 1로 시작하는지 검사
2. 이전에 방문했는지 체크
3. dfs 탐색 시작
   3.1 visited 처리
   3.2 사방탐색 조건검사
   • 배열의 유효값인지
   • 방문을 했는지
   • 해당 단지의 값이 '1' 인지
     3.3 조건검사까지 무사하다면 dfs 탐색 재귀 이용
4. 나온 값들을 종합해서 ArrayList넣고 정렬후 출력

코드는 다음과 같다

package DFS;
import java.io.*;
import java.util.*;
public class 단지번호붙이기 {

	static int[][] array;
	static int[][] visited;
	static int result;
	static int[] dx = new int[] {0,0,1,-1};
	static int[] dy = new int[] {1,-1,0,0};
	static int k;
	public static void main(String[] args) throws Exception {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		ArrayList<Integer> a = new ArrayList<>();
		k = Integer.parseInt(br.readLine());
		array = new int[k][k];
		visited = new int[k][k];
		for(int i=0;i<k;i++) {
			String line = br.readLine();
			for(int j=0;j<k;j++) {
				int qw = line.charAt(j)-'0';
				array[i][j] = qw;
			}
		}
		
		for(int i=0;i<k;i++) {
			for(int j=0;j<k;j++) {
				result = 0;
				if(visited[i][j]==1) continue;
				if(array[i][j]==0) continue;
				dfs(i,j);
				a.add(result);
			}
		}
		
		Collections.sort(a);
		System.out.println(a.size());
		for(int q : a) {
			System.out.println(q);
		}
	}
	
	public static void dfs(int x, int y) {
		
		visited[x][y] = 1;
		result++;
		
		for(int i=0;i<4;i++) {
			int cx = x+dx[i];
			int cy = y+dy[i];
			
			if(cx<0 || cx>=k || cy<0 || cy>=k) continue;
			if(visited[cx][cy]==1) continue;
			if(array[cx][cy]==0) continue;
			dfs(cx,cy);
			
		}
		
	}

이런문제만 나오면 얼마나좋을까.. 얼른 골드 5~골드3까지 도전해보자