매일 Algorithm

백준 2583번 (그래프 탐색)

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;

public class problem222 {
    static int n; // 높이
    static int m; // 너비
    static int q; // 직사각형 갯수
    static int[][] map;

    static int[] dx = {-1, 1, 0, 0}; // 상 하
    static int[] dy = {0, 0, -1, 1}; // 좌 우
    static int count; // 분리된 넓이

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

        n = in.nextInt();
        m = in.nextInt();
        q = in.nextInt();

        map = new int[n][m];

        // 한칸당 넓이가 1임으로, 바인딩한다.
        for (int i = 0; i < q; i++) {
            int x1 = in.nextInt();
            int y1 = in.nextInt();
            int x2 = in.nextInt();
            int y2 = in.nextInt();

          // 입력값에 따른 범위 지정 (y부터 반복문을 하는 이유, 열(n)이 y값 임으로)
            for (int j = y1; j < y2; j++) {
                for (int k = x1; k < x2; k++) {
                    map[j][k] = 1;
                }
            }
        }

        List<Integer> list = new ArrayList<>();
        // 분리된 영역 넓이
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (map[i][j] == 0) {
                    count = 0; // 초기화
                    DFS(i, j);
                    // 분리된 영역 넓이값 저장
                    list.add(count);
                }
            }
        }
        System.out.println(list.size());

        Collections.sort(list);
        for (int result : list) {
            System.out.print(result + " ");
        }
    }

    private static void DFS(int a, int b) {
        map[a][b] = 1; // 방문 확인
        count++;

        for (int i = 0; i < 4; i++) {
            // 상하좌우 노드를 확인한다.
            int nowX = a + dx[i];
            int nowY = b + dy[i];
            if (nowX >= 0 && nowY >= 0 && nowX < n && nowY < m) {
                if (map[nowX][nowY] == 0) {
                    DFS(nowX, nowY);
                }
            }
        }

    }
}

백준 2210번 (그래프 탐색)

import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;

public class problem223 {

    static int[][] map;
    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};
    static Set<String> set = new HashSet<>();
    static int count;

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

        map = new int[5][5];

        for (int i = 0; i < 5; i++) {
            for (int j = 0; j < 5; j++) {
                map[i][j] = in.nextInt();
            }
        }

        // x위치, y위치 (전체의 경우의수를 확인한다)
        String st = " ";
        for (int i = 0; i < 5; i++) {
            for (int j = 0; j < 5; j++) {
                DFS(i, j, 0, st);
            }
        }

        System.out.println(set.size());

    }

    private static void DFS(int x, int y, int count, String str) {
        // 6자리씩 끊어서 확인한다.
        if (count == 6) {
            set.add(str);
            return;
        }

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

            // 범위안의 값인지 확인
            if (nowX >= 0 && nowX < 5 && nowY >= 0 && nowY < 5) {
                // 문자열 + 정수 = 문자로 반환
                DFS(nowX, nowY, count + 1, str + map[nowX][nowY]);
            }
        }
    }
}

백준 1783번 (그리디)

import java.util.Scanner;

public class problem224 {

    static int n;
    static int m;

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

        n = in.nextInt();
        m = in.nextInt();
        System.out.print(result());
    }

    private static int result() {
        if (n == 1) {
            return 1; // 해당 서있는 위치 1번 카운트
        }
        if (n == 2) {
            // 이동 횟수가 4번까지는 제약 X
            // 2열 일때 최대 이동 가능 횟수는 4이다.
            return Math.min(4, (m + 1) / 2);
        }
        if (m < 7) {
            // 3열 이상, 7행 보다 낮을 경우는 최대 4번 이동 가능
            return Math.min(4, m);
        }
        return m - 2;
    }
}