https://www.acmicpc.net/problem/2667
2667번: 단지번호붙이기
<그림 1>과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여
www.acmicpc.net
풀기 전:
dfs로 들어가면서 0으로 바꿔주며 dfs 들어가질 때마다 count 해준다
그리고 count를 arrayList에 추가해 주다가 정렬해서 출력
import java.io.*;
import java.util.*;
class Main {
static int count;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
StringTokenizer st;
int N = Integer.parseInt(br.readLine());
int[][] graph = new int[N][N];
for (int i = 0; i < N; i++) {
String Line = br.readLine();
for (int j = 0; j < N; j++)
graph[i][j] = Integer.parseInt(String.valueOf(Line.charAt(j)));
}
/////////////////////////////////////////////////////////////////////////////////무난하게 입력받고
ArrayList<Integer> arrayList = new ArrayList<>();
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (graph[i][j] == 1) {
count = 0;
bfs(graph, i, j, N);
arrayList.add(count);
}
}
}
Collections.sort(arrayList);
sb.append(arrayList.size() + "\n");
for (int i = 0; i < arrayList.size(); i++)
sb.append(arrayList.get(i) + "\n");
System.out.println(sb);
}
public static void bfs(int[][] graph, int i, int j, int N) {
count++;
graph[i][j] = 0;
if (i != N - 1 && graph[i + 1][j] == 1)
bfs(graph, i + 1, j, N);
if (i != 0 && graph[i - 1][j] == 1)
bfs(graph, i - 1, j, N);
if (j != N - 1 && graph[i][j + 1] == 1)
bfs(graph, i, j + 1, N);
if (j != 0 && graph[i][j - 1] == 1)
bfs(graph, i, j - 1, N);
}
}
bfs 때리고 정답들끼리 정렬
굉장히 쉬운 문제였다