[백준 / Java] 2667번 단지번호붙이기

사용한 알고리즘 (DFS)

DFS 

https://cobi-98.tistory.com/30

[필수 알고리즘] DFS 깊이 우선 탐색 (Stack 구조) 이해

 

🔒 2667번 단지번호 붙이기

✔ 문제 설명

🚩 요구사항 분석

• 해당 위치에서 상하좌우 판단
• 정사각형 지도 배열
• 방문기록 필요
• 단지수, 단지에 속하는 집의 수 오름차순 -> list.size() , sort 정렬

 

🔑 문제풀이

입력으로 들어오는 값이 String 이므로 한 칸씩 잘라서 map에 저장한다. ( char타입이므로 -'0' 처리)

방문할 때마다 count++하여 집의 개수를 추가한다.

방향배열 int x, int y 파라미터 적용

상 좌 하 우 위치 이동 시 n*n배열의 크기보다 작아야 호출

map [nx][ny] = 1이고 (집이 있고) visit [nx][ny] = false로 아직 방문하지 않았다면 dfs 메서드를 재귀적으로 호출하여 방문수행

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;

public class Main {
    public static int N; // n각형 지도
    static int[] dx = {1, -1, 0, 0};
    static int[] dy = {0, 0, 1, -1};
    public static boolean[][] visit;
    public static ArrayList<Integer> arr = new ArrayList<>(); // 단지내 집의 수를 담고있는 배열
    public static int[][] map;
    public static int cnt;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());

        map = new int[N][N];
        visit = new boolean[N][N];

        for (int i = 0; i < N; i++) {
            String st = br.readLine();
            for (int j = 0; j < N; j++) {
                map[i][j] = st.charAt(j) - '0';
            }
        }

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (map[i][j] == 1 && !visit[i][j]) {
                    cnt = 1;
                    dfs(i, j);
                    arr.add(cnt);
                }
            }
        }
        System.out.println(arr.size());
        Collections.sort(arr);
        for (int i = 0; i < arr.size(); i++) {
            System.out.println(arr.get(i));
        }
    }

    public static void dfs(int x, int y) {

        if(!visit[x][y]){
            return;
        }

        visit[x][y] = true;

        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];

            if (nx >= 0 && nx < N && ny >= 0 && ny < N) { //한 단지 내에서 dfs 호출
                if (map[nx][ny] == 1 && !visit[nx][ny]) {

                    dfs(nx, ny);
                    cnt++;
                }
            }
        }
    }
}