[DFS/BFS] 백준 - 2583번: 영역 구하기 Java 풀이

[공부용이기 때문에 코드가 깔끔하지 않을 수 있습니다!]

 

2583번: 영역 구하기

 

 

문제 풀이는 다음과 같다.

5 x 7 사이즈의 맵이 있고

그 안에 삼각형 3개가 있다.(겹칠 수 있음)

 

그리고 3개의 삼각형의 크기를 입력받는데

0, 2 지점부터 4, 4 지점까지의 크기가 있다고 입력받는다.

 

이렇게 2번 더 걸쳐 총 3번을 받게 된다.

 

그리고 맵에서 빈 곳을 세어서 총 몇 개의 빈 곳이 있는지와 그 빈 곳의 개수를 오름차순으로 정렬하여 출력하면 된다.

 

코드(DFS)

//DFS

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    static int n;
    static int m;
    static boolean[][] map;
    static boolean[][] visited;
    static int dx[] = {-1, 1, 0, 0};
    static int dy[] = {0, 0, -1, 1};
    static List<Integer> nums;
    static int count;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());

        map = new boolean[n][m];
        visited = new boolean[n][m];
        nums = new ArrayList<>();
        count = 0;

        for (int i = 0; i < k; i++) {
            st = new StringTokenizer(br.readLine());
            int a1 = Integer.parseInt(st.nextToken());
            int b1 = Integer.parseInt(st.nextToken());
            int a2 = Integer.parseInt(st.nextToken()) - 1;
            int b2 = Integer.parseInt(st.nextToken()) - 1;


            for (int j = a1; j <= a2; j++) {
                for (int l = b1; l <= b2; l++) {
                    map[l][j] = true;
                }
            }
        }

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (!visited[i][j] && !map[i][j]) {
                    dfs(i, j);
                    nums.add(count);
                    count = 0;
                }
            }
        }

        Collections.sort(nums);
        System.out.println(nums.size());
        for (Integer num : nums) {
            System.out.print(num + " ");
        }
    }

    private static void dfs(int x, int y) {
        visited[x][y] = true;
        count++;

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

            if (nowX >= 0 && nowY >= 0 && nowX < n && nowY < m) {
                if (!visited[nowX][nowY] && !map[nowX][nowY]) {
                    dfs(nowX, nowY);
                }
            }
        }
    }
}

 

코드(BFS)

//BFS

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    static int n;
    static int m;
    static boolean[][] map;
    static boolean[][] visited;
    static int dx[] = {-1, 1, 0, 0};
    static int dy[] = {0, 0, -1, 1};
    static List<Integer> nums;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());

        map = new boolean[n][m];
        visited = new boolean[n][m];
        nums = new ArrayList<>();

        for (int i = 0; i < k; i++) {
            st = new StringTokenizer(br.readLine());
            int a1 = Integer.parseInt(st.nextToken());
            int b1 = Integer.parseInt(st.nextToken());
            int a2 = Integer.parseInt(st.nextToken()) - 1;
            int b2 = Integer.parseInt(st.nextToken()) - 1;


            for (int j = a1; j <= a2; j++) {
                for (int l = b1; l <= b2; l++) {
                    map[l][j] = true;
                }
            }
        }

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (!visited[i][j] && !map[i][j]) {
                    int num = bfs(i, j);
                    nums.add(num);
                }
            }
        }

        Collections.sort(nums);
        System.out.println(nums.size());
        for (Integer num : nums) {
            System.out.print(num + " ");
        }
    }

    private static int bfs(int x, int y) {
        visited[x][y] = true;
        int count = 1;
        Queue<int[]> q = new LinkedList<>();
        q.add(new int[]{x, y});

        while (!q.isEmpty()) {
            int[] list = q.poll();
            int xx = list[0];
            int yy = list[1];

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

                if (nowX >= 0 && nowY >= 0 && nowX < n && nowY < m) {
                    if (!visited[nowX][nowY] && !map[nowX][nowY]) {
                        visited[nowX][nowY] = true;
                        q.add(new int[]{nowX, nowY});
                        count++;
                    }
                }
            }
        }

        return count;
    }
}