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이 아닌 값을 출력
반응형
'PS > boj' 카테고리의 다른 글
boj)2178 - 미로 탐색 (0) | 2020.09.03 |
---|---|
boj)1012 - 유기농 배추 (0) | 2020.09.03 |
boj)2606 - 바이러스 (0) | 2020.09.03 |
boj)1260 - DFS와 BFS (0) | 2020.09.03 |
boj)18352 - 특정 거리의 도시 찾기 (0) | 2020.09.02 |