kingsubin

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

public class Main {
    static int n, danjiCnt;
    static int[][] graph = new int[26][26];
    static int[] num = new int[26*26];

    static boolean dfs (int x, int y) {
        if (x < 1 || x > n || y < 1 || y > n) {
            return false;
        }

        // 단지가 될 수 있다면
        if (graph[x][y] == 1) {
            graph[x][y] = 0;
            num[danjiCnt]++;

            dfs(x - 1, y);
            dfs(x + 1, y);
            dfs(x, y - 1);
            dfs(x, y + 1);

            return true;
        }

        return false;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());

        // graph 입력
        for (int i = 1; i <= n; i++) {
            String str = br.readLine();
            for (int j = 1; j <= n; j++) {
                graph[i][j] = str.charAt(j-1) - '0';
            }
        }

        // graph 순회하면서 dfs 실행
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (dfs(i, j)) {
                    danjiCnt++;
                }
            }
        }
	       
        // 출력 
        System.out.println(danjiCnt);
        Arrays.sort(num);
        for (int value : num) {
            if (value != 0) {
                System.out.println(value);
            }
        }
        
    }
}

- 얼음 채우기에서 봤던 느낌이랑 비슷해서 DFS로 접근했다.

- 삽질하면서 시간도 많이쓰고 정답을 맞추긴했는데 버거웠따 ...

- 바로 넘어가지말고 다른 사람풀이를 봐서 생각 따라가는거 연습해보자

 

 

1. 사용 할 변수 선언

1-1) int n, danjiCnt / int[26][26] graph 

int num[26*26] : 처음엔 num[26]이었고 런타임오류가 떠서 다시 코드를봤는데 26으로 하면 25x25로 가장 큰 배열일때

그 danjiCnt 가 26을 넘어버릴수도 있기에 크게 잡음. 약간 낭비일수도있는데 몇으로 잡아야 할지 생각이 안났다.

 

2. 입력받고 dfs 함수 생성

2-1) 상하좌우로 움직일건데 만약에 x, y가 graph의 범위를 넘을경우 false

2-2) 그래프 탐색부분이 1일경우에 거기서 부터 같은 단지를 전부 탐색하기 위해 상하좌우로 dfs 호출

2-3) 이미 방문한곳은 0으로 만들어주고 num[danjiCnt]++;을 해준다 -> 한 단지에 있는 아파트 수 카운팅

 

3. 메인함수에서 dfs 호출

3-1) 모든 배열에서 dfs를 돌아야하니까 이중 for문 사용

3-2) 만약에 dfs 함수가 true값을 반환하면 하나의 단지를 이뤘다는거니까 danjiCnt++;

 

4. 출력

4-1) 단지수 호출

4-2) 단지별 아파트를 오름차순으로 출력해야 하기에 Arrays.sort()로 오름차순 정렬후 0이 아닌 값을 출력

 

 

---

www.acmicpc.net/problem/2667