포스트

영역 구하기

게시
By Gilbert Jung
7 분읽는 시간
영역 구하기

문제 파악

문제

🔖 백준(실버1) - 영역 구하기

백준(실버1) - 그림 과 유사한 문제이다.


주요 조건

• 이번 문제는 분리된 각 영역의 면적과 그 갯수를 구하는 문제이다.


아이디어

우선 주어진 좌표 x1, y1, x2, y2 를 가지고 인접행렬을 만들어야 한다.

넓이에 포함된 좌표는 1로 나타내고 그렇지 않은 영역은 0으로 나타낸다.

그리고 0으로 나타낼 좌표는 x1 ~ x2, y1 ~ y2 사이 범위의 좌표가 이에 해당된다.

이번 문제는 주어진 좌표를 통해 연결된 지점을 찾는 것이 중요 포인트다.

그리고 이 문제의 경우는 모든 노드를 방문해야 하는 문제이기 때문에 DFS,BFS 모두 구현이 가능하다.

마지막으로 각 지역의 넓이는, 연결된 노드로 넘어갈 경우 count + 1을 해준다.

이때 방문배열을 꼭 확인해야 함을 숙지해야 한다.


문제 해결 과정

핵심 로직

• 좌표를 사용해서 인접행렬을 생성한다.


해결 순서

⒈ 좌표의 범위를 활요하여 인접행렬 생성

⒉ BFS 또는 DFS 로직 수행


소스 코드

🔖 DFS 풀이

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119

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

public class 영역구하기DFS2583 {

    static int M,N,K;
    static int x1,y1,x2,y2, count;
    static int[][] graph;
    static boolean[][] visited;
    static int[] dx = {0, 0, -1, 1};
    static int[] dy = {1, -1, 0, 0};
    static List<Integer> areaList = new ArrayList<>();

    public static void main(String[] args) throws IOException {
        generateMatrixAndVisited();

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                Position pos = new Position(i,j);
                if (isNeverVisited(pos)) {
                    count = 0;
                    addAreaToList(pos);
                }
            }
        }
        Collections.sort(areaList);
        printAnswer();
    }

    private static class Position {

        private int row;
        private int col;

        public Position(int row, int col) {
            this.row = row;
            this.col = col;
        }

        public int getRow() {
            return this.row;
        }

        public int getCol() {
            return this.col;
        }
    }

    private static boolean isNeverVisited(Position position) {
        return !visited[position.getRow()][position.getCol()] && graph[position.getRow()][position.getCol()] == 0;
    }

    private static void addAreaToList(Position position) {
        int area = dfs(position);
        areaList.add(area);
    }

    private static void generateMatrixAndVisited() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        M = Integer.parseInt(st.nextToken());
        N = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());

        graph = new int[N][M];
        visited = new boolean[N][M];

        for (int i = 0; i < K; i++) {
            st = new StringTokenizer(br.readLine(), " ");

            x1 = Integer.parseInt(st.nextToken());
            y1 = Integer.parseInt(st.nextToken());
            x2 = Integer.parseInt(st.nextToken());
            y2 = Integer.parseInt(st.nextToken());


            for (int x = x1; x < x2; x++) {
                for (int y = y1; y < y2; y++) {
                    graph[x][y] = 1;
                }
            }
        }
    }

    private static int dfs(Position pos) {

        visited[pos.getRow()][pos.getCol()] = true;
        count++;

        for (int i = 0; i < dx.length; i++) {
            int nextRow = pos.getRow() + dx[i];
            int nextCol = pos.getCol() + dy[i];

            Position nextPos = new Position(nextRow, nextCol);

            if (isInRange(nextPos)) {
                dfs(nextPos);
            }
        }
        return count;
    }

    private static boolean isInRange(Position nextPos) {
        if (nextPos.getRow() >= 0 && nextPos.getRow() < N && nextPos.getCol() >= 0 && nextPos.getCol() < M
                && !visited[nextPos.getRow()][nextPos.getCol()] && graph[nextPos.getRow()][nextPos.getCol()] == 0) {
            return true;
        }
        return false;
    }

    private static void printAnswer() {
        System.out.println(areaList.size());
        System.out.println(areaList.stream().map(i -> String.valueOf(i)).collect(Collectors.joining(" ")));
    }
}


🔖 BFS 풀이

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130

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

public class 영역구하기2583BFS {

    static int M,N,K;
    static int x1,y1,x2,y2;
    static int[][] graph;
    static boolean[][] visited;
    static int[] dx = {0, 0, -1, 1};
    static int[] dy = {1, -1, 0, 0};
    static List<Integer> areaList = new ArrayList<>();

    public static void main(String[] args) throws IOException {
        generateMatrixAndVisited();

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                Position pos = new Position(i,j);
                if (isNeverVisited(pos)) {
                    addAreaToList(pos);
                }
            }
        }
        Collections.sort(areaList);
        printAnswer();
    }

    private static class Position {

        private int row;
        private int col;

        public Position(int row, int col) {
            this.row = row;
            this.col = col;
        }

        public int getRow() {
            return this.row;
        }

        public int getCol() {
            return this.col;
        }
    }

    private static boolean isNeverVisited(Position position) {
        return !visited[position.getRow()][position.getCol()] && graph[position.getRow()][position.getCol()] == 0;
    }

    private static void addAreaToList(Position position) {
        int area = bfs(position);
        areaList.add(area);
    }

    private static void generateMatrixAndVisited() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        M = Integer.parseInt(st.nextToken());
        N = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());

        graph = new int[N][M];
        visited = new boolean[N][M];

        for (int i = 0; i < K; i++) {
            st = new StringTokenizer(br.readLine(), " ");

            x1 = Integer.parseInt(st.nextToken());
            y1 = Integer.parseInt(st.nextToken());
            x2 = Integer.parseInt(st.nextToken());
            y2 = Integer.parseInt(st.nextToken());


            for (int x = x1; x < x2; x++) {
                for (int y = y1; y < y2; y++) {
                    graph[x][y] = 1;
                }
            }
        }
    }

    private static int bfs(Position pos) {

        int count = 1;
        Queue<Position> q = new LinkedList<>();
        q.offer(pos);

        while (!q.isEmpty()) {
            Position currentPosition = q.poll();
            int curRow = currentPosition.getRow();
            int curCol = currentPosition.getCol();

            visited[curRow][curCol] = true;

            for (int i = 0; i < dx.length; i++) {
                int nextRow = curRow + dx[i];
                int nextCol = curCol + dy[i];

                Position nextPos = new Position(nextRow, nextCol);

                if (isInRange(nextPos)) {

                    visited[nextRow][nextCol] = true;
                    count ++;
                    q.offer(nextPos);
                }
            }
        }
        return count;
    }

    private static boolean isInRange(Position nextPos) {
        if (nextPos.getRow() >= 0 && nextPos.getRow() < N && nextPos.getCol() >= 0 && nextPos.getCol() < M
                && !visited[nextPos.getRow()][nextPos.getCol()] && graph[nextPos.getRow()][nextPos.getCol()] == 0) {
            return true;
        }
        return false;
    }

    private static void printAnswer() {
        System.out.println(areaList.size());
        System.out.println(areaList.stream().map(i -> String.valueOf(i)).collect(Collectors.joining(" ")));
    }
}
algorithm
이 기사는 저작권자의 CC BY 4.0 라이센스를 따릅니다.