99클럽 코테 스터디 18일차 TIL + 오늘의 학습 키워드

☑️ 문제: 단지번호붙이기

https://www.acmicpc.net/problem/2667

 

☑️ Code: DFS

import java.util.*;

public class solution {
    static int N;
    static boolean[][] empty;
    static boolean[][] visited;
    static int complexCount;
    static int[] houseCount;

    static class Point {
        int row, col;
        Point(int row, int col) {
            this.row = row;
            this.col = col;
        }
    }

    public static void main(String[] args) {
        init();
        solve();
    }

    private static void solve() {
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (!empty[i][j] && !visited[i][j]) {
                    dfs(i, j);
                    complexCount++;
                }
            }
        }

        System.out.println(complexCount);
        Arrays.sort(houseCount, 0, complexCount); // 오름차순 출력 조건
        for (int i = 0; i < complexCount; i++) {
            System.out.println(houseCount[i]);
        }
    }

    private static void dfs(int row, int col) {
        int[] dr = { 1, 0, -1, 0 };
        int[] dc = { 0, 1, 0, -1 };

        // stack 선언 및 초기화
        Stack<Point> stack = new Stack<>();
        stack.push(new Point(row, col));

        while(!stack.isEmpty()) { // dfs
            Point point = stack.pop();
            row = point.row;
            col = point.col;

            if (!visited[row][col]) {
                visited[row][col] = true;
                houseCount[complexCount]++;

                for (int i = 0; i < 4; i++) {
                    int nextRow = row + dr[i];
                    int nextCol = col + dc[i];

                    if (!noRange(nextRow, nextCol) && !empty[nextRow][nextCol] && !visited[nextRow][nextCol]) {
                        stack.push(new Point(nextRow, nextCol));
                    }
                }
            }
        }
    }

    private static boolean noRange(int r, int c) {
        return r < 0 || r >= N || c < 0 || c >= N;
    }

    private static void init() {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        sc.nextLine();

        // input array (0: empty or 1: !empty)
        empty = new boolean[N][N];
        for (int i = 0; i < N; i++) {
            String line = sc.nextLine();
            for (int j = 0; j < N; j++) {
                empty[i][j] = line.charAt(j) - '0' == 0;
            }
        }
        visited = new boolean[N][N];

        // complex(단지) count & house(집)
        complexCount = 0;
        houseCount = new int[(N * N) / 2 + 1]; // 최대 단지 개수만큼 할당
    }
}

 

☑️ Notes: Java에서의 Stack

• Stack<T> stack = new Stack<>(); : stack 선언 및 초기화
• stack.push(value): 삽입
• stack.pop(): 반환 및 삭제