SW 역량테스트 - [백준] 영역 구하기 문제 풀이/해답/코드 (C++ / JAVA)

---

SW 역량 테스트 준비를 위한 핵심 문제들을 다룹니다!

해답을 보기 전에 문제를 풀어보시거나, 설계를 하고 오시는 것을 추천드립니다. 

코드에 대한 설명은 주석을 참고해 주세요 :)

 

---

문제 링크 : www.acmicpc.net/problem/2583

해답 코드 : 

 

#include<iostream>
#include <vector>
#include <algorithm>


using namespace std;

typedef struct pos {
	int row;
	int col;
} pos;

int M, N, K;
int divided;

int map[100][100];
pos rec[100][2];


// up, right, down, left
int dX[4] = { 0, 1, 0, -1 };
int dY[4] = { -1, 0, 1, 0 };




bool isRange(int x, int y) {
	if (x < 0 || x >= M || y < 0 || y >= N) return false;
	else return true;
}


void paint() {

	// 왼쪽 위 꼭짓점
	int left_row;
	int left_col;

	// 오른쪽 아래 꼭짓점
	int right_row;
	int right_col;


	for (int num_rec = 0; num_rec < K; num_rec++) {

		left_row = rec[num_rec][1].row;
		left_col = rec[num_rec][0].col;

		right_row = rec[num_rec][0].row;
		right_col = rec[num_rec][1].col;

		for (int i = left_row; i <= right_row; i++) {
			for (int j = left_col; j <= right_col; j++) {
				map[i][j] = -1;
			}
		}

	}

}


void dfs_visit(int cur_row, int cur_col) {

	if (map[cur_row][cur_col] != 0) {
		return;
	}

	int next_r;
	int next_c;

	// paint
	map[cur_row][cur_col] = divided;

	// try next move
	for (int i = 0; i < 4; i++) {

		next_r = cur_row + dX[i];
		next_c = cur_col + dY[i];

		if (isRange(next_r, next_c) && map[next_r][next_c] == 0) {
			dfs_visit(next_r, next_c);
		}

	}

}


int main(int argc, char** argv)
{
	int test_case;
	int T;
	/*
	   아래의 freopen 함수는 input.txt 를 read only 형식으로 연 후,
	   앞으로 표준 입력(키보드) 대신 input.txt 파일로부터 읽어오겠다는 의미의 코드입니다.
	   //여러분이 작성한 코드를 테스트 할 때, 편의를 위해서 input.txt에 입력을 저장한 후,
	   freopen 함수를 이용하면 이후 cin 을 수행할 때 표준 입력 대신 파일로부터 입력을 받아올 수 있습니다.
	   따라서 테스트를 수행할 때에는 아래 주석을 지우고 이 함수를 사용하셔도 좋습니다.
	   freopen 함수를 사용하기 위해서는 #include <cstdio>, 혹은 #include <stdio.h> 가 필요합니다.
	   단, 채점을 위해 코드를 제출하실 때에는 반드시 freopen 함수를 지우거나 주석 처리 하셔야 합니다.
	*/
	
	//FILE *fp;
	//freopen_s(&fp, "sample_input.txt", "r", stdin);
	//cin >> T;
	/*
	   여러 개의 테스트 케이스가 주어지므로, 각각을 처리합니다.
	*/

		cin >> M >> N >> K;

		divided = 1;

		// position of rectangles

		// get position of the rectangles
		int temp1, temp2;
		for (int i = 0; i < K; i++) {

			// left-below
			cin >> temp1 >> temp2;
			rec[i][0].col = temp1;
			rec[i][0].row = M - temp2 - 1;

			// right-top
			cin >> temp1 >> temp2;
			rec[i][1].col = temp1 - 1;
			rec[i][1].row = M - temp2;
		}

		// paint the map -> visited = -1
		paint();

		vector<int> areas;

		// visit the map (DFS)
		// If the map is 0, paint to 1, 2, 3 ... -> # of the area divided
		for (int i = 0; i < M; i++) {
			for (int j = 0; j < N; j++) {
				if (map[i][j] == 0) {
					dfs_visit(i, j);
					areas.push_back(0);
					divided++;
				}
			}
		}
		
		// count the areas
		for (int i = 0; i < M; i++) {
			for (int j = 0; j < N; j++) {
				if (map[i][j] > 0) {
					areas[map[i][j]-1]++;
				}
			}
		}

		cout << areas.size() << "\n";
		
		sort(areas.begin(), areas.end());

		cout << areas[0];
		for (int i = 1; i < areas.size(); i++) {
			cout << " " << areas[i];
		}

	
	return 0;//정상종료시 반드시 0을 리턴해야합니다.
}

 

SW 역량테스트 준비 - [모의 SW 역량테스트] 풀이 / 코드 / 답안 (C++ / JAVA)

SW 역량테스트 준비 - C++ 코드, Java 코드

SW 역량테스트 준비 - 백준 알고리즘 문제