BOJ_2667_단지번호 붙이기

1.

구분: BFS, DFS

언어: Java

전략:

• 기본적인 BFS, DFS의 기본 유형으로 푼다. 
• 여기서 핵심 각 단지 내, 개수(total)를 재귀 함수를 부를 때마다 하나 씩 더한다.
• 또는 재귀 함수의 파라미터로 count값을 전달하여 마지막에 return하는 형식이다.    

---

2. 코드

import java.util.*;
public class BOJ_2667 {

	static int[][]map;
	static int cnt, n, total;
	public static void main(String[] args) {
    
		Scanner scanner = new Scanner(System.in);
		n = scanner.nextInt();
		map = new int[n][n];
		
		for(int i = 0; i<n; i++) {
			String str = scanner.next();
			for(int j = 0; j<n; j++) {
				map[i][j] = str.charAt(j)-'0';
			}
		}
		Queue<Integer> q= new LinkedList<Integer>();
		for(int i = 0; i<n; i++) {
			for(int j = 0; j<n; j++) {
				if(map[i][j] == 1) {
					total=1;
					cnt++;
					dfs(i, j);
					q.offer(total);
				}
			}
		}
		
		int[] result = new int[cnt];
		for(int i = 0; i<cnt; i++) {
			result[i] = q.poll();
		}
		
        Arrays.sort(result);
		System.out.println(cnt);
		
        for(int i : result) {
			System.out.println(i);
		}
	}//main
	
	
	public static void dfs(int y, int x) {
		
		map[y][x] = 0;
		for(int d = 0; d<4; d++) {
			int ny = y + dy[d];
			int nx = x + dx[d];
			
			if(nx<0 || ny<0 || nx>=n || ny>=n) continue;
			if(map[ny][nx]==0) continue;
			
			total+=1;
			dfs(ny, nx);
			
		}
	
	}
	
	public static int dfs2(int y, int x, int count) {
		map[y][x] = 0;
		for(int d = 0; d<4; d++) {
			int ny = y + dy[d];
			int nx = x + dx[d];
			
			if(nx<0 || ny<0 || nx>=n || ny>=n) continue;
			if(map[ny][nx]==0) continue;
			
			count = dfs2(ny, nx, count+1);
		}
		
		return count;
	}
	
 
	
	
	static int[] dx = {1,0,-1,0};
	static int[] dy = {0,-1,0,1};

}

---

3. 

• 가장 기본적인 유형이다.
• 기본 유형을 잘 익히면 사용할 수 있고, 다만 각 단지내의 개수를 구하는 부분이 생소하다.