단지번호붙이기

 

---

 

문제 설명

 

 

 

입출력 예시

 

 

요약

아파트 단지의 개수와 각 단지에 속한 아파트 개수 구하기

 

---

 

풀이

 

접근 방식

1. 전체 단지의 모습을 담은 이차원 배열 graph 작성

  → 전체 사이즈는 N+2로 설정(상하좌우 탐색을 위해 1~N 까지의 전체 단지를 둘러싸는 크기로 설정)

  → 1 : true, 0 : false로 아파트가 있는 곳 표시

 

2. 단지 개수 구하기

  → graph의 첫 번째 row부터 순차적으로 방문하면서 true인 곳을 false로 변경

  → 상하좌우 탐색 전 첫 방문시 단지 count ++

 

3. 단지 내 아파트 개수 구하기

  → 상하좌우 탐색해가며 true인 곳을 방문(dfs)

  → 방문 시 마다 아파트 count++

  → 방문한 곳은 graph에서 false로 변경

 

---

 

코드리뷰

 

import java.util.*;

public class Main {
    static boolean[][] graph;
    static int countApt = 0;
    static int[] posRow = {0, 0, -1, 1};	// 상, 하 탐색을 위한 배열
    static int[] posCol = {1, -1, 0, 0};	// 좌, 우 탐색을 위한 배열

    public static void main(String[] args) {
        List<Integer> list = new ArrayList<>();
        int countGroup = 0;
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        
        graph = new boolean[N+2][N+2];	// 1~N까지의 단지 전체를 둘러싸기 위한 N+2 크기의 graph 생성
        
        for(int i = 1; i <= N; i++) {
            String s = sc.next();
            for(int j = 1; j <= N; j++) {
                if(s.charAt(j-1) == '1') {	// 1일 경우 true
                    graph[i][j] = true;
                }
            }
        }

        for(int i = 1; i <= N; i++) {
            for(int j = 1; j <= N; j++) {
                if(graph[i][j]) {	// 아파트가 있다면
                    countGroup++;	// 우선 그룹 count 증가
                    countApt = 0;	// 해당 단지의 아파트 개수 초기화
                    dfs(i, j);	// 재귀함수 호출
                    list.add(countApt);	// 상하좌우 탐색 종료 후 아파트의 개수 list에 add
                }
            }
        }
        Collections.sort(list);	// 오름차순 정렬
        System.out.println(countGroup);	// 단지 개수 출력
        for(int i : list) {
            System.out.println(i);	// 아파트 개수 출력
        }
        sc.close();
    }

    static void dfs(int row, int col) {	// 상하좌우 탐색 재귀함수 메소드
        countApt++;	// 아파트 count 증가
        graph[row][col] = false;	// 재방문 방지를 위해 해당 좌표를 false로 변경
        for(int i = 0; i < 4; i++) {	// 상하좌우 탐색
            int COL = col + posCol[i];	// i = 0일 때 좌, i = 1일 때 우
            int ROW = row + posRow[i];	// i = 2일 때 상, i = 3일 때 하
            if(graph[ROW][COL]) {
                dfs(ROW, COL);	// 상하좌우 탐색 시 아파트가 존재하면 방문
            }
        }
    }
}

 

 

 

* refs

https://www.youtube.com/watch?v=SLZ3Tqvgurg