[백준알고리즘] 2583번 : 영역 구하기 #스터디 2주차

문제는 아래 사이트에 들어가면 확인 할 수 있다. 

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

2583번: 영역 구하기

 

예제 입력을 확인해보면 띄어쓰기로 각 값을 구분하는 것을 확인할 수 있다. 

첫째줄에는  M, N, K 를 입력,

그 후 K줄만큼 입력받는다.

두번째줄부터 입력받은 것은, 왼쪽 아래 꼭짓점 좌표의 x, y, 오른쪽 위 꼭짓점 좌표의 x, y이다. 

 

여기에서 주의할 점은 우리가 흔히 생각하는 배열의 0,0 과 좌표 표시하는 값이 완전히 다르다는 점이다. 

문제의 그림을 보면 왼쪽 아래가 0,0이고 오른쪽 위가 N,M이다. 

 

 

 

먼저 선언한 변수 및 배열들이다.

N : 전체 배열 크기 N*N을 위한 변수

paper [max][max] : 모눈종이 용 배열, 직사각형이 그려진 곳인지의 여부를 표시

visit[max][max] : 방문 체크용 배열, 같은 위치를 순회하지 못하게 체크해주기 위함

int pos[4][2] : 상하좌우 좌표를 위한 변수

countN : 단지 내의 몇개의 집이 있는지 체크하기 위한 변수

int N : 행의 개수

int M : 열의 개수

int K : 직사각형의 개수

vector<int> v : 직사각형이 없는 부분들 순회 완료후 주변끼리 묶어 주었을 때의 개수 보관 , 한 칸의 넓이가 1이므로 개수를 보관하면 그 칸들의 넓이로 사용할 수 있다. 

 

 

먼저 M, N, K를 입력 한 후, leftBottom X와 Y, right Top X, Y역시 입력받는다. 

반복문을 통해 paper배열에 직사각형의 구역인지 체크해주었다.  

 

 

paper[0][0]부터  paper[m][n]까지 반복하면서 체크해주었다. 

1) 직사각형 영역이 아닌지 체크 : paper[y][x] == 0인가?

2) 방문하지 않았는지 체크 : !visit[y][x] 인가?

 

두가지 조건을 통해 dfs를 시작한다. 

countN을 0으로 초기화하고 dfs내부에서 한 구역을 들어갈 때마다 증가시켜준다. 

dfs에서 재귀호출을 해주기 때문에 dfs에서 리턴후에 countN의 값은  주변끼리 묶어 주었을 때의 개수가 된다. 

그 값을 vector v에 추가해주었다.

 

 

dfs 함수에선 현재 위치를 받고, countN을 증가시켰다. 

방문여부 체크 후에 pos를 이용해 상하좌우 탐색을 시작한다. 

 

1) 배열 내부인가.

2) 값이 0인가

3) 방문하지 않았는가 

 

세가지 조건을 확인 후 재귀호출을 해주었다. 

 

 

 

마지막으로 v.size()를 통해 몇개의 묶음이 생성되었는지 출력해주었다. 

 

또 v.size()만큼 반복하여, 각 묶음에 몇개의 칸이 들어있는지 출력했다. 한칸의 넓이가 1이므로 몇개의 칸인지 출력해주면 그 넓이를 출력하는 효과가 된다. 

 

 

 

 

<전체 코드>

 

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

#include <iostream> #include <cstring> #include <vector> #include <algorithm> using namespace std;   #define MAX 100 int paper[MAX][MAX] = { 0 }; //모눈종이: 2차원 배열생성 0으로 초기화 int visit[MAX][MAX]; int pos[4][2] = { {0,1},{0,-1},{-1,0},{1,0} }; //상하좌우 int countN; int N, M, K; vector<int> v;   void dfs(int y, int x) {     countN++;     visit[y][x] = true;       for (int i = 0; i < 4; i++) {         int ny = y + pos[i][0];         int nx = x + pos[i][1];         if (ny >= 0 && ny < M && nx >= 0 && nx < N && paper[ny][nx] == 0 && !visit[ny][nx]) dfs(ny, nx);     } } int main() {     cin >> M >> N >> K;     for (int i = 0; i < K; i++) {         int lbX, lbY, rtX, rtY; //left bottom x, y  & right top x, y         cin >> lbX >> lbY >> rtX >> rtY;         for (int y = lbY; y < rtY; y++)             for (int x = lbX; x < rtX; x++)                 paper[y][x] = 1;     }     for (int y = 0; y < M; y++) {         for (int x = 0; x < N; x++) {             if (paper[y][x] == 0 && !visit[y][x]) { //방문하지 않았는가, 값이 0인가 확인                 countN = 0; // 각 영역의 넓이 확인위한 초기화                 dfs(y,x);                 v.push_back(countN);             }         }     }     cout << v.size() << "\n";     sort(v.begin(), v.end());       for (int i = 0; i < v.size(); i++) {         cout << v[i] << ' ';     }       return 0; } Colored by Color Scripter

cs