매일 Algorithm

백준 15729번 (그리디)

import java.util.Scanner;

public class problem271 {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int size = in.nextInt();
        int[] arr = new int[size + 2];

        for (int i = 0; i < size; i++) {
            arr[i] = in.nextInt();
        }

        int result = 0;
        for(int i = 0; i < size; i++) {
            if(arr[i] == 1) {
            // 현재 배열의 인덱스 값이 1이면 
            // 다음 인덱스 다다음 인덱스를 한번의 횟수로 친다.
                result++;
                if (arr[i + 1] == 1) {
                    arr[i + 1] = 0;
                }
                else {
                    arr[i + 1] = 1;
                }
                if (arr[i + 2] == 1) {
                    arr[i + 2] = 0;
                }
                else {
                    arr[i + 2] = 1;
                }
            }
        }

        System.out.print(result);
    }
}

백준 25214번 (그리디)

import java.util.Scanner;

public class problem272 {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int size = in.nextInt();
        int result = 0;
        int min = Integer.MAX_VALUE;
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < size; i++) {
            int n = in.nextInt();
            if (min > n) {
                min = n; // min 값 갱신
            } else {
                result = Math.max(result, n - min); // 최대값 반환
            }
            sb.append(result).append(' ');
        }
        System.out.print(sb.toString());
    }
}

백준 1012번 (그래프 이론)

import java.util.Scanner;

public class problem273 {
    static int n;
    static int m;
    static int t;
    static int count;
    static int[][] graph;
    static boolean[][] visit;
    static int result;
    static int[] moveX = {0, 0, -1, 1};
    static int[] moveY = {-1, 1, 0, 0};


    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);


        t = in.nextInt(); // 테스트 갯수


        for (int i = 0; i < t; i++) {
            result = 0; // 결과값 초기화
            n = in.nextInt(); // 행의 갯수
            m = in.nextInt(); // 열의 갯수
            count = in.nextInt(); // 배추가 심어져있는 위치 갯수
            graph = new int[n][m];
            visit = new boolean[n][m];
            for (int j = 0; j < count; j++) {
                int x = in.nextInt();
                int y = in.nextInt();
                graph[x][y] = 1; // 배추가 있는 위치를 1로 초기화
            }

            for (int k = 0; k < n; k++) {
                for (int p = 0; p < m; p++) {
                    // 배열 크기만큼 탐색한다.
                    if (!visit[k][p] && graph[k][p] == 1) {
                        DFS(k, p);
                        result++;
                    }
                }
            }
            System.out.println(result);
        }


    }

    private static void DFS(int x, int y) {
        visit[x][y] = true; // 방문처리

        for (int i = 0; i < 4; i++) {
            int mX = x + moveX[i];
            int mY = y + moveY[i];

            // 값 범위 검증
            if (mX >= 0 && mX < n && mY >= 0 && mY < m) {
                // 방문 X, 배추가있는지 검증
                if (!visit[mX][mY] && graph[mX][mY] == 1) {
                    DFS(mX, mY);
                }
            }
        }

    }
}

백준 2667번 (그래프 이론)

import java.util.Arrays;
import java.util.Scanner;

public class problem274 {
    static int n;
    static int[][] graph;
    static boolean[][] visit;
    static int[] total = new int[25*25]; // 기본 틀 크기
    static int[] moveY = {-1, 1, 0, 0};
    static int[] moveX = {0, 0, -1, 1};
    static int result = 0;

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);

        n = in.nextInt();
        graph = new int[n][n];
        visit = new boolean[n][n];

        for (int i = 0; i < n; i++) {
            String str = in.next();
            for (int j = 0; j < n; j++) {
                graph[i][j] = str.charAt(j) - '0';
            }
        }

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (graph[i][j] == 1 && !visit[i][j]) {
                    result++;
                    DFS(i, j);
                }
            }
        }
        Arrays.sort(total);
        System.out.println(result); // 총 단지수
        for (int i = 0; i < total.length; i++) {
            if (total[i] == 0) {
                continue;
            } else {
                System.out.println(total[i]); // 각 단지내의 집의 수
            }
        }
    }

    private static void DFS(int x, int y) {
    	// 방문 처리
        visit[x][y] = true; 
        
        // DFS가 호출 될때까지는 집이 이어져 있다는 뜻임으로, 증가
        total[result]++; 

        // 상하좌우 이동, 검증
        for (int i = 0; i < 4; i++) {
            int mX = x + moveX[i];
            int mY = y + moveY[i];

            // 범위 검증, 방문 검증
            if (mX >= 0 && mX < n && mY >= 0 && mY < n) {
                if (!visit[mX][mY] && graph[mX][mY] == 1) {
                    DFS(mX, mY);
                }
            }
        }
    }
}