문제이해
이 문제는 2차원 배열이 주어지고, 인접한 원소의 총 개수(집의 개수)와 인접한 원소로 이루어진 그룹의 수(단지의 수)를 구하는 문제입니다.
배추문제와 다른점은, 배추문제에서는 배추의 좌표를 직접 X와 Y로 받았다면, 이 문제에서는 집의 위치정보를 0과 1로 이루어진 문자열로 입력받습니다.
2차원 배열 탐색
문제를 풀다보면 2차원 배열 탐색 문제에서는 물어보는게 비슷한데 보통 아래의 두가지를 물어봅니다.
- 인접한 원소의 개수를 세는 문제
- 인접한 원소로 이루어진 그룹의 수를 세는 문제 (덩어리 수라고 이해하면 쉬움)
2차원 배열 탐색 문제를 풀기 위해 필요한 공통 능력들은 아래와 같습니다.
- 입력값 처리 후 탐색할 board 구현
- 올바른 위치에 count ++; 대입
- 방향배열을 이용하여 현재 위치에서 상하좌우 배열값 탐색
- 문제에 따른 BFS / DFS 선택
-
2차원 배열에서의 탐색은, 모든 배열을 순회하며 현재 위치를 기준으로 상하좌우를 탐색해야하고 이는 방향배열을 선언하여 이용해주면 됩니다.
-
문제에 따라 카운트를 세주면 되는데, 카운트 하는 위치와 초기화에 주의해야 합니다.
-
원소의 개수를 셀 때는 DFS 함수가 호출되는 횟수를 세면 되고, 덩어리를 셀 때는 DFS를 처음 호출하는 시점에 카운트를 증가시키면 됩니다.
문제접근
이 문제는 단지의 수와 집의 수를 구하는 문제입니다.
배추의 2차원 배열 상 위치값을 입력으로 받았던 배추문제와 달리, 집의 위치를 0과 1로 이루어진 문자열로 받습니다.
charAt()를 이용해주었는데, 각 행의 특정 열에 있는 문자를 2차원 배열에 넣어주어야 하기 때문에 i가 아닌 j를 써주어야 합니다.
board[i][j] = s.charAt(j)
ㅋㅋ 정말 틀린곳이 없는데 자꾸 틀렸다길래 찾느라 너무 힘들었다 힝구리ㅠㅠ
값들을 배열에 넣어주고 탐색을 진행해주면 되는데 저는 DFS를 이용해주었습니다.
단지의 수를 countNum 집의 수를 countHouse 으로 선언해주어 카운트해줬습니다.
결과값 출력을 위해 List객체를 생성해주고, 각 단지에 대한 CountHouse값을 저장한 이후에 Collection.sort()를 이용하여 정렬 이후에 모든 원소를 출력해주면 됩니다.
code
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.ArrayList;
import java.util.Collections;
public class Main{
static int[][] board;
static int dx[] = {-1,1,0,0};
static int dy[] = {0,0,-1,1};
static int n;
static int countHouse;
static ArrayList<Integer> ans;
static boolean[][] visited;
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
n = Integer.parseInt(br.readLine());
board = new int[n][n];
visited = new boolean[n][n];
ans = new ArrayList<>();
for(int i=0; i<n; i++){
String s = br.readLine();
for(int j=0; j<n; j++){
board[i][j] = s.charAt(j) - '0';
}
}
int countNum =0;
for(int i=0; i<n; i++){
for(int j=0; j<n; j++){
if( board[i][j] == 1 && !visited[i][j]){
countHouse = 0; // 집의 수 초기화
DFS(i,j);
ans.add(countHouse); // 집의 갯수
countNum ++; // 단지의 수
}
}
}
System.out.println(countNum);
Collections.sort(ans);
for(int i : ans){
System.out.println(i);
}
}
private static void DFS(int x, int y){
visited[x][y] = true;
countHouse++;
for(int i=0; i<4; i++) {
int mx = x + dx[i];
int my = y + dy[i];
if (mx >= 0 && mx < n && my >= 0 && my < n) {
if (board[mx][my] == 1 && !visited[mx][my]) {
DFS(mx, my);
}
}
}
}
}
