[JAVA] 백준 2667 단지번호붙이기 (BFS, DFS)

 

📝 문제

📎 백준 2667 단지번호붙이기

2667번: 단지번호붙이기

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


// 단지 번호 붙이기 //
// bfs, dfs

public class Baek_2667 {
    static int[] dx = {-1,0,1,0};
    static int[] dy = {0,1,0,-1};
    static int N;
    static int[][] map,copymap;
    static boolean[][] visited;

    static int hcount = 0;          // 각 단지의 수를 저장할 변수

    static void house(int x,int y) {        // 단지의 개수 출력
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[] {x,y});
        map[x][y] = 0;
        visited[x][y] = true;

        while(!queue.isEmpty()) {
            int[] now = queue.poll();
            for(int i=0; i<4; i++) {
                int nx = now[0] + dx[i];
                int ny = now[1] + dy[i];
                if(nx>=0 && nx<N && ny>=0 && ny<N && map[nx][ny] != 0 && !visited[nx][ny]) {
                    map[nx][ny] = 0;
                    visited[nx][ny] = true;
                    queue.offer(new int[] {nx,ny});
                    house(nx,ny);
                }
            }
        }
    }


    static int housecount(int x,int y,int[][] copymap) {        // 각 단지내 집의 수 출력
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[] {x,y});
        copymap[x][y] = 0;
        hcount ++;

        while(!queue.isEmpty()) {
            int[] now = queue.poll();
            for(int i=0; i<4; i++) {
                int nx = now[0] + dx[i];
                int ny = now[1] + dy[i];
                if(nx>=0 && nx<N && ny>=0 && ny<N && copymap[nx][ny] != 0) {
                    copymap[nx][ny] = 0;
                    queue.offer(new int[] {nx,ny});
                    housecount(nx,ny,copymap);
                }
            }
        }
        return hcount;      // 처음 1을 만나서 0으로 만들때까지의 1의 개수를 반환
    }



    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        ArrayList<Integer> arrayList = new ArrayList<>();
        N = Integer.parseInt(bf.readLine());
        map = new int[N][N];        //  원본 배열 , 단지수를 찾기 위한 배열
        copymap = new int[N][N];    // 원본 배열과 같은 배열 , 단지에 속하는 집의 수를 찾기 위한 배열
        visited = new boolean[N][N];
        int count = 0;      // 단지의 수를 저장할 변수

        // 1. 단지의 개수 찾기
        for(int i=0; i<N; i++) {
            String line = bf.readLine();
            for(int j=0; j<N; j++) {
                map[i][j] = line.charAt(j) - '0';
            }
        }

        for(int i=0; i<N; i++) {
            for(int j=0; j<N; j++) {
                if(map[i][j] == 1 ) {
                    count ++;
                    house(i,j);
                }
            }
        }
        System.out.println(count);      // 총 단지의 개수 출력


        // 2. 단지내 집의 개수 찾기
        for(int i=0; i<N; i++) {
            copymap[i] = map[i].clone();    // 원본배열을 깊은복사로 복사 - 원본배열에 영향 X
        }

        // 각 단지내 집의 수를 찾는다.
        for(int i=0; i<N; i++) {
            for(int j=0; j<N; j++) {
                if(copymap[i][j] == 1) {        // 집(1)이면
                    arrayList.add(housecount(i,j,copymap));     // 반환된 집의 수를 리스트에 저장
                    hcount = 0;             // hcount 초기화
                }
            }
        }

        Collections.sort(arrayList);    // 오름차순 정렬
        for(int i=0; i<arrayList.size(); i++) {
            System.out.println(arrayList.get(i));   // 각 단지내 집의 수를 오름차순으로 정렬하여 출력
        }
    }
}

 

✅ 문제설명

• 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여기서 연결되었다는 것은 어떤 집이 좌우, 혹은 아래위로 다른 집이 있는 경우를 말한다. 대각선상에 집이 있는 경우는 연결된 것이 아니다. 지도를 입력하여 단지수를 출력하고, 각 단지에 속하는 집의 수를 오름차순으로 정렬하여 출력하는 프로그램을 작성하시오.

 

내가 생각한 문제에서 주의해야 할 만한 제약조건은!!

1. "단지에 속하는 집의 수를 오름차순으로 정렬" 부분
2. 배열을 입력받을 때 붙여서 입력받는 부분

 

<입력>
7
0110100
0110101
1110101
0000111
0100000
0111110
0111000

<출력>
3
7
8
9

✅ 문제 접근

• 단지수를 출력하는 부분은 백준 4938 섬의 개수 와 거의 같기 때문에 비슷하게 구현했다.
  ⭐️ 섬의개수 github 코드 ⭐️
• 생각할 부분은 단지에 속하는 집의 수를 출력하는 부분이었는데 배열을 복사하고 함수를 하나 더 만든 후 배열에서 1을 만나면 0으로 지워주고 카운트를 늘려가는 방식의 코드를 구현했다. 

 

함수

• house(int x,int y) : 백준 4936번 섬의개수문제와 같은 알고리즘 적용 , 단지의 수를 출력하기위한 함수
• housecount(int x,int y,int[][] copymap) : 원본배열(map)을 복사한 배열(copymap)을 for루프로 돌면서 1을 만나면 불리는 함수,
  1을 0으로 바꾼 후 hcount 를 늘려주고 마지막에 hcount를 반환해준다. 

---

❓ charAt()- '0'

방법

• Stirng의 charAt() 메소드를 사용
• text.charAt(i) : 해당 문자열의 i번째 인덱스 값을 char 형으로 반환한다.
• 만약 숫자가 입력되었을 경우, '0' 을 빼주어 유니코드 값이 아닌 int형으로 바꾸어야 한다.

❓배열의 오름차순 정렬

📎 문서참고

자바 List 정렬하는 방법(오름차순, 내림차순)

• arraylist를 선언하고 housecount(int x,int y,int[][] copymap) 로 반환되는 hcount 를 arraylist에 추가하였다. 
• Collections.sort(arrayList); 를 통해 list를 오름차순으로 정렬하였다. 
• arrayList.get() 을 사용해 정렬된 list를 출력한다.
• arraylist에 추가한 후 hcount = 0 으로 초기화하여 새로운 housecount(int x,int y,int[][] copymap) 로 반환되는 hcount 의 값을 받도록 하였다.

 

// 각 단지내 집의 수를 찾는다.
for(int i=0; i<N; i++) {
  for(int j=0; j<N; j++) {
     if(copymap[i][j] == 1) {  // 집(1)이면
       arrayList.add(housecount(i,j,copymap));   // 반환된 집의 수를 리스트에 저장
       hcount = 0;   // hcount 초기화
       }
   }
}

Collections.sort(arrayList);    // 오름차순 정렬
for(int i=0; i<arrayList.size(); i++) {
   System.out.println(arrayList.get(i));   // 각 단지내 집의 수를 오름차순으로 정렬하여 출력
}