코딩하는 두꺼비

www.acmicpc.net/problem/17144

미세먼지 확산 구현보다 공기청정기 순환을 구현하는 것이 생각보다 까다로웠던 문제이다.

미세먼지 확산의 경우 임시적으로 맵을 한개 더 만들고 확산값을 저장한 후 기존의 값에 다시 더해주는 형식으로 구현하였다.

공기청정기 바람 순환은 위쪽 4개 + 아래쪽 4개를 각각 포문을 사용하여 구현하였으며 임시값 두개를 사용해 값을 교환해주면서 진행하였으며 각각의 범위를 정하는 것이 까다로워서 시간이 오래걸렸다.

공기청정기 구현만 조심하면 어려운 문제는 아니었던 것 같다.

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int R, C, T, ans;
int map1[51][51];
int map2[51][51];
int dx[4] = { 0,1,0,-1 };
int dy[4] = { 1,0,-1,0 };
pair<int, int> ac;

void spread() {
	int tmp = 0;
	int cnt = 0;
	for (int i = 0; i < R; i++) {
		for (int j = 0; j < C; j++) {
			if (map1[i][j] >= 5) {
				tmp = map1[i][j] / 5;
				for (int k = 0; k < 4; k++) {
					int nx = i + dx[k];
					int ny = j + dy[k];
					if (nx >= 0 && ny >= 0 && nx < R 
						&& ny < C && map1[nx][ny] != -1) {
						cnt++;
						map2[nx][ny] += tmp;
					}
				}
				map1[i][j] -= tmp * cnt;
			}
			tmp = 0;
			cnt = 0;
		}
	}
	for (int i = 0; i < R; i++) {
		for (int j = 0; j < C; j++) {
			map1[i][j] += map2[i][j];
			map2[i][j] = 0;
		}
	}
	return;
}

void rotate() {
	int tmp = 0, tmp2 = 0;
	int x = ac.first;
	tmp = map1[x][1];
	map1[x][1] = 0;
	for (int i = 2; i < C; i++) {
		tmp2 = map1[x][i];
		map1[x][i] = tmp;
		tmp = tmp2;
	}
	for (int i = x-1; i >= 0; i--) {
		tmp2 = map1[i][C - 1];
		map1[i][C - 1] = tmp;
		tmp = tmp2;
	}
	for (int i = C - 2; i >= 0; i--) {
		tmp2 = map1[0][i];
		map1[0][i] = tmp;
		tmp = tmp2;
	}
	for (int i = 1; i < x; i++) {
		tmp2 = map1[i][0];
		map1[i][0] = tmp;
		tmp = tmp2;
	}
	x += 1;
	tmp = 0, tmp2 = 0;
	tmp = map1[x][1];
	map1[x][1] = 0;
	for (int i = 2; i < C; i++) {
		tmp2 = map1[x][i];
		map1[x][i] = tmp;
		tmp = tmp2;
	}
	for (int i = x + 1; i <= R - 1; i++) {
		tmp2 = map1[i][C - 1];
		map1[i][C - 1] = tmp;
		tmp = tmp2;
	}
	for (int i = C - 2; i >= 0; i--) {
		tmp2 = map1[R - 1][i];
		map1[R - 1][i] = tmp;
		tmp = tmp2;
	}
	for (int i = R - 2; i > x; i--) {
		tmp2 = map1[i][0];
		map1[i][0] = tmp;
		tmp = tmp2;
	}
	return;
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int check = 0;
	cin >> R >> C >> T;
	for (int i = 0; i < R; i++) {
		for (int j = 0; j < C; j++) {
			cin >> map1[i][j];
			if (map1[i][j] == -1 && check == 0) {
				check = 1;
				ac.first = i;
			}
		}
	}
	while (T--) {
		spread();
		rotate();
	}
	for (int i = 0; i < R; i++) {
		for (int j = 0; j < C; j++) {
			if (map1[i][j] > 0) {
				ans += map1[i][j];
			}
		}
	}
	cout << ans;
	return 0;
}

www.acmicpc.net/problem/15686

재귀로 풀지 조합으로 풀지 고민하다가 조합으로 푼 문제이다. 다른 사람들 풀이를 보니 재귀로 많이 풀어낸 것 같다.

단순히 치킨거리를 구하는 게 아니라 치킨집을 몇개 선정하고 최소 치킨 거리를 구해야 해서 조금 까다로웠다.

처음에 모든 치킨 거리의 수를 계산해서 배열에 저장하고 M개의 치킨집은 벡터에 0 나머지는 1을 넣고 그 조합벡터를

next_permutation을 사용해 풀어냈다.

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int N, M, ans = 99999;
int map[51][51];
vector<pair<int, int>> home;
vector<pair<int, int>> chick;
int htoc[101][14];
vector<int> open;

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int tmp, tmp2;
	cin >> N >> M;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			cin >> map[i][j];
			if (map[i][j] == 1) {
				home.push_back({ i,j });
			}
			if (map[i][j] == 2) {
				chick.push_back({ i,j });
			}
		}
	}
	for (int i = 0; i < home.size(); i++) {
		for (int j = 0; j < chick.size(); j++) {
			htoc[i][j] = abs(home[i].first - chick[j].first) + abs(home[i].second - chick[j].second);
		}
	}
	for (int i = 0; i < chick.size(); i++) {
		if (i < M) {
			open.push_back(0);
		}
		else {
			open.push_back(1);
		}
	}
	do {
		tmp2 = 0;
		for (int i = 0; i < home.size(); i++) {
			tmp = 9999;
			for (int j = 0; j < chick.size(); j++) {
				if (open[j] == 0) {
					tmp = min(tmp, htoc[i][j]);
				}
			}
			tmp2 += tmp;
		}
		ans = min(tmp2, ans);
	} while (next_permutation(open.begin(), open.end()));

	cout << ans;
	return 0;
}

www.acmicpc.net/problem/15683

처음에 단순히 각각의 최대값들만 계산하게 구현했다가 안되서 한동안 코테 공부를 소홀하게 만든 문제이다..

단순 구현 문제임에도 고려해야 될 사항들이 많은 문제라 많이 어려웠다.(내 생각엔 최악의 문제이다..ㅠㅠ)

고민하다가 결국 재귀로 해결할 수 있었고 모든 경우의 수를 브루트 포스와 비슷하게 다 고려하여 풀었다.

각 cctv의 시야 범위를 7로 바꾸는 부분은 바킹독님의 풀이를 참고하여 수정하였다.

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;

int N, M, ans = 987654;

int map2[10][10];
int cam2[2][2] = { {1,3},{2,4} };
int cam3[4][2] = { {1,2},{2,3},{3,4},{1,4} };
int cam4[4][3] = { {1,2,3},{2,3,4},{1,3,4},{1,2,4} };
int dx[4] = { 0, 1, 0, -1 };
int dy[4] = { 1, 0, -1,0 };
vector<pair<int, int>> v;


void cpy(int(*map1)[10]) {
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			map2[i][j] = map1[i][j];
		}
	}
}

void cpy2(int (*map1)[10]) {
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			map1[i][j] = map2[i][j];
		}
	}
}

void check(int x, int y, int dir) {
	while (1) {
		x += dx[dir-1];
		y += dy[dir-1];
		if (x < 0 || y < 0 || x >= N || y >= M || map2[x][y] == 6) {
			return;
		}
		if (map2[x][y] != 0) {
			continue;
		}
		map2[x][y] = 7;
	}
}

void dfs(int cnt) {
	int map1[10][10];
	cpy2(map1);
	if (cnt == v.size()) {
		int k = 0;
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				if (map2[i][j] == 0) {
					k++;
				}
			}
		}
		ans = min(ans, k);
		return;
	}
	
	int x = v[cnt].first;
	int y = v[cnt].second;
	if (map2[x][y] == 1) {
		for (int i = 1; i <= 4; i++) {
			cpy2(map1);
			check(x, y, i);
			cnt++;
			dfs(cnt);
			cnt--;
			cpy(map1);
		}
	}
	else if (map2[x][y] == 2) {
		for (int i = 0; i < 2; i++) {
			cpy2(map1);
			for (int j = 0; j < 2; j++) {
				check(x, y, cam2[i][j]);
			}
			cnt++;
			dfs(cnt);
			cnt--;
			cpy(map1);
		}
	}
	else if (map2[x][y] == 3) {
		for (int i = 0; i < 4; i++) {
			cpy2(map1);
			for (int j = 0; j < 2; j++) {
				check(x, y, cam3[i][j]);
			}
			cnt++;
			dfs(cnt);
			cnt--;
			cpy(map1);
		}
	}
	else if (map2[x][y] == 4) {
		cpy2(map1);
		for (int i = 0; i < 4; i++) {
			for (int j = 0; j < 3; j++) {
				check(x, y, cam4[i][j]);
			}
			cnt++;
			dfs(cnt);
			cnt--;
			cpy(map1);
		}
	}
	else {
		cpy2(map1);
		for (int i = 1; i <= 4; i++) {
			check(x, y, i);
		}
		cnt++;
		dfs(cnt);
		cnt--;
		cpy(map1);
	}
	return;
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin >> N >> M;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			cin >> map2[i][j];
			if (map2[i][j] != 0 && map2[i][j] != 6) {
				v.push_back({ i,j });
			}
		}
	}
	dfs(0);
	
	cout << ans;
}

www.acmicpc.net/problem/14499

처음엔 어떻게 풀어야할지 아예 감이 안잡히는 문제였다.

주사위를 구현해야하는데 방향까지 고려해서 구현을 해야한다고 생각을 했었다.

하지만 전개도 번호를 고정으로 잡고 그 안의 값들만 변경 시켜서 구현하니 바로 풀리는 문제였다.

각각 동서남북으로 이동하면서 조건 확인 및 좌표수정, 주사위 바닥면을 복사해주고, 주사위 면들을 옮겼다.

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int N, M, x, y, K;
int map[21][21];
int dice[7];

void cp(int a) {	//주사위 바닥면 복사
	if (map[x][y] == 0) {
		map[x][y] = dice[a];
	}
	else {
		dice[a] = map[x][y];
		map[x][y] = 0;
	}
}

int main() {
	int z, tmp;
	cin >> N >> M >> x >> y >> K;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			cin >> map[i][j];
		}
	}
	for (int i = 0; i < K; i++) {
		cin >> z;
		if (z == 1) {	//동쪽 이동
			if (y + 1 < M) {
				y++;
				cp(3);
				tmp = dice[1];
				dice[1] = dice[3];
				dice[3] = dice[6];
				dice[6] = dice[4];
				dice[4] = tmp;
				cout << dice[6] << "\n";
			}
		}
		else if (z == 2) {	//서쪽 이동
			if (y - 1 >= 0) {
				y--;
				cp(4);
				tmp = dice[1];
				dice[1] = dice[4];
				dice[4] = dice[6];
				dice[6] = dice[3];
				dice[3] = tmp;
				cout << dice[6] << "\n";
			}
		}
		else if (z == 3) {		//북쪽 이동
			if (x - 1 >= 0) {
				x--;
				cp(2);
				tmp = dice[1];
				dice[1] = dice[2];
				dice[2] = dice[6];
				dice[6] = dice[5];
				dice[5] = tmp;
				cout << dice[6] << "\n";
			}
		}
		else {
			if (x + 1 < N) {	//남쪽 이동
				x++;
				cp(5);
				tmp = dice[1];
				dice[1] = dice[5];
				dice[5] = dice[6];
				dice[6] = dice[2];
				dice[2] = tmp;
				cout << dice[6] << "\n";
			}
		}
	}
	return 0;
}

www.acmicpc.net/problem/16234

구현 문제이자 BFS로서 생각보다 크게 어렵진 않았지만 배열 크기 선언과 범위 설정하느라

계속 틀리다가 맞추었다. N*N으로 배열을 선언해야하는데 그 생각을 못하고 그냥 N으로 선언한 것이 패착이였다.

실제 시험장에서는 항상 변수 선언을 할때 생각을 하면서 해야할거 같다..

풀이는 BFS로 연합의 개수를 세고 각 2차원 배열로 각 연합의 인구수를 계산해서 저장을 해놓고

마지막에 인구수를 나눈 값을 넣어주는 형식으로 구성했다.

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
#include <algorithm>
using namespace std;

int N, L, R, ans, cnt = 1;
int map[51][51];
int visit[51][51];
int people[2555][2];
int dx[4] = { 0, 1, 0, -1 };
int dy[4] = { 1, 0, -1, 0 };
queue<pair<int, int>> q;

void bfs(int x, int y) {
	q.push({ x, y });
	visit[x][y] = cnt;
	people[cnt][1]++;
	people[cnt][0] += map[x][y];

	while (!q.empty()) {
		int s = q.size();
		for (int i = 0; i < s; i++) {
			int a = q.front().first;
			int b = q.front().second;
			q.pop();
			for (int j = 0; j < 4; j++) {		//국경을 열 수 있는지 확인
				int c = a + dx[j];
				int d = b + dy[j];
				if (c >= 0 && d >= 0 && c < N && d < N && visit[c][d] == 0 
					&& abs(map[a][b] - map[c][d]) >= L
					&& abs(map[a][b] - map[c][d]) <= R) {
					q.push({ c, d });
					visit[c][d] = cnt;
					people[cnt][0] += map[c][d];
					people[cnt][1]++;
				}
			}
		}
	}
	return;
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin >> N >> L >> R;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			cin >> map[i][j];
		}
	}
	while (1) {
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				if (visit[i][j] == 0) {
					bfs(i, j);
					cnt++;	//연합 갯수 증가
				}
			}
		}
		for (int i = 0; i < N; i++) {	//연합 안의 사람들 재분배
			for (int j = 0; j < N; j++) {
				if (visit[i][j] > 0) {
					map[i][j] = people[visit[i][j]][0] / people[visit[i][j]][1];
				}
			}
		}
		if (cnt > N * N) {	//연합의 갯수가 N*N이면 중단
			break;
		}
		ans++;
		cnt = 1;
		memset(people, 0, sizeof(people));	//배열 초기화
		memset(visit, 0, sizeof(visit));
	}
	cout << ans;
	return 0;
}

www.acmicpc.net/problem/14500

처음엔 경우의 수를 적게 생각하고 풀어서 계속 틀린 문제이다.

천천히 대칭을 포함한 경우의 수 19가지를 생각하고 그에 맞게 최대값을 구해주었다.

나 같은 경우에는 크게 5가지로 나누었다.

네모 모양 1가지 경우의 수를 계산하고

3개짜리 테트리스에 1개를 모든 방향에 붙인다는 생각으로 크게 2가지, 작게 7가지씩 14가지를 구성하였고

또한 2개짜리에 2개를 붙이는 경우를 2개씩 총 4가지를 계산해주었다.

#define _CRT_SECURE_NO_WARINGS
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int map[501][501];
int N, M, ans, temp;

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin >> N >> M;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			cin >> map[i][j];
		}
	}
	for (int i = 0; i < N - 1; i++) {	// 네모모양 계산
		for (int j = 0; j < M - 1; j++) {
			ans = max(ans, map[i][j] + map[i + 1][j + 1] + map[i + 1][j] + map[i][j + 1]);
		}
	}
	for (int i = 0; i < N - 2; i++) {	//세로 3개짜리에 1개 붙이기
		for (int j = 0; j < M; j++) {
			temp = map[i][j] + map[i + 1][j] + map[i + 2][j];
			if (i + 3 < N) {
				ans = max(ans, temp + map[i + 3][j]);
			}
			if (j - 1 >= 0) {
				ans = max(ans, temp + map[i][j - 1]);
				ans = max(ans, temp + map[i + 1][j - 1]);
				ans = max(ans, temp + map[i + 2][j - 1]);
			}
			if (j + 1 < M) {
				ans = max(ans, temp + map[i][j + 1]);
				ans = max(ans, temp + map[i + 1][j + 1]);
				ans = max(ans, temp + map[i + 2][j + 1]);
			}
		}
	}
	for (int i = 0; i < N; i++) {	//가로 3개짜리에 1개 붙이기
		for (int j = 0; j < M - 2; j++) {
			temp = map[i][j] + map[i][j + 1] + map[i][j + 2];
			if (j + 3 < M) {
				ans = max(ans, temp + map[i][j + 3]);
			}
			if (i - 1 >= 0) {
				ans = max(ans, temp + map[i - 1][j]);
				ans = max(ans, temp + map[i - 1][j + 1]);
				ans = max(ans, temp + map[i - 1][j + 2]);
			}
			if (i + 1 < N) {
				ans = max(ans, temp + map[i + 1][j]);
				ans = max(ans, temp + map[i + 1][j + 1]);
				ans = max(ans, temp + map[i + 1][j + 2]);
			}
		}
	}
	for (int i = 0; i < N - 2; i++) {	//세로 2개짜리에 2개 붙이기
		for (int j = 0; j < M; j++) {
			temp = map[i][j] + map[i + 1][j];
			if (j - 1 >= 0) {
				ans = max(ans, temp + map[i+1][j - 1] + map[i + 2][j - 1]);
			}
			if (j + 1 < M) {
				ans = max(ans, temp + map[i+1][j + 1] + map[i + 2][j + 1]);
			}
		}
	}
	for (int i = 0; i < N; i++) {		//가로 2개짜리에 2개 붙이기
		for (int j = 0; j < M - 2; j++) {
			temp = map[i][j] + map[i][j + 1];
			if (i + 1 < N) {
				ans = max(ans, temp + map[i + 1][j + 1] + map[i + 1][j + 2]);
			}
			if (i - 1 >= 0) {
				ans = max(ans, temp + map[i - 1][j + 1] + map[i - 1][j + 2]);
			}
		}
	}
	cout << ans << "\n";
}

www.acmicpc.net/problem/3190

삼성 기출문제를 풀기 시작하여 첫문제로 정한 구현문제이다.

처음엔 조건을 보고 약간 겁먹었는데

천천히 조건을 보고 각 칸을 뱀의 몸, 사과, 빈 공간, 벽으로 나누었고

뱀은 덱을 사용해 구현하였다.

또한 다음 위치를 항상 저장하고 방향변수 및 시간 변수를 사용해서 풀었고

방향 전환을 할때 현재 방향을 고려하여 방향을 바꿔주었다.

#define _CRT_SECURE_NO_WARINGS
#include <iostream>
#include <deque>
#include <vector>
#include <algorithm>
using namespace std;

int N, K, L, cnt;		//기본 변수 3개, 시간변수
int dv, tv;		//방향변수, 방향전환 벡터 위치변수
int map[102][102];
deque<pair<int, int>> snake;
vector <pair<int, char>> v;

int main() {
	int a, b;
	char c;
	cin >> N;
	cin >> K;
	for (int i = 0; i < K; i++) {
		cin >> a >> b;
		map[a][b] = 1;
	}
	cin >> L;
	for (int i = 0; i < L; i++) {
		cin >> a >> c;
		v.push_back({ a,c });
	}
	a = 1, b = 2;
	snake.push_back({ 1, 1 });	//초기 뱀 세팅
	map[1][1] = 3;
	for (int i = 0; i <= N + 1; i++) {	//초기 벽 세팅
		map[0][i] = 2;
		map[i][0] = 2;
		map[i][N + 1] = 2;
		map[N + 1][i] = 2;
	}
	while (1) {
		snake.push_front({ a,b });	//뱀 머리 넣기
		cnt++;
		if (map[a][b] == 0) {		//공간이 빈 경우
			map[snake.front().first][snake.front().second] = 3;
			map[snake.back().first][snake.back().second] = 0;
			snake.pop_back();
		}
		else if (map[a][b] == 1) {		//사과가 있는 경우
			map[snake.front().first][snake.front().second] = 3;
		}
		else {		//뱀의 몸이나 벽일 경우
			break;
		}
		if (tv < v.size() && cnt == v[tv].first) {		//방향전환
			if (v[tv].second == 'L') {		//왼쪽
				if (dv == 0) {
					dv = 3;
				}
				else {
					dv -= 1;
				}
			}
			else {		//오른쪽
				if (dv == 3) {
					dv = 0;
				}
				else {
					dv += 1;
				}
			}
			tv++;
		}
		if (dv == 0) {		//다음 칸 이동
			b++;
		}
		else if (dv == 1) {
			a++;
		}
		else if (dv == 2) {
			b--;
		}
		else {
			a--;
		}
	}
	cout << cnt << "\n";
	return 0;
}

www.acmicpc.net/problem/13458

쉬운 문제임에도 불구하고 시간초과와 변수 크기 때문에 꽤나 애먹었다..

또한 올림/내림 함수를 까먹어서 찾았고 또한 int형 숫자 두개를 나누면 절대 double형으로 결과값이 나오지 않는 다는 것도 알게 되었다.

오랜만에 푸는 문제였는데 브론즈임에도 불구하고 유의해야 할 점이 많이 있어서 기록하게 되었다.

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <vector>
#include <cmath>
#include <algorithm>
using namespace std;

long long N, A, B, ans;
double C;
vector<double> lec;

int main() {
	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> A;
		lec.push_back(A);
	}
	cin >> B >> C;
	ans += N;
	for (int i = 0; i < N; i++) {
		lec[i] -= B;
		if (lec[i] > 0) {
			ans += ceil(lec[i] / C);
		}
	}
	cout << ans << "\n";
	return 0;
}

www.acmicpc.net/problem/1992

분할 정복의 대표격인 문제인 쿼드 트리이다.

예전에 프로그래머스 월간 챌린지에서 비슷한 문제가 나온적이 있었다. 그땐 개념을 제대로 몰라 막 풀었는데 이번에는 재귀를 사용해서 푸는 법을 알게 되어 이를 사용해 풀 수 있었다.

괄호를 넣어줘야되는 부분이 좀 까다로워서 고민을 많이 했는데 함수 호출전에 미리 넣어주는 방식으로 해결할 수 있었다.

이전에 Z라는 문제를 풀었는데 그때 답지를 보며 공부한 것이 크게 도움되었다.

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;

int N;
int quad[65][65];
string ans;

void dfs(int x, int y, int z) {
	int check = 0;
	for (int i = x; i < x + z; i++) {
		for (int j = y; j < y + z; j++) {
			if (quad[x][y] != quad[i][j]) {
				check = 1;
				break;
			}
		}
	}
	if (check == 0) {
		ans += to_string(quad[x][y]);
	}
	else {
		z = z / 2;
		ans += "(";
		if (z == 1) {
			ans += to_string(quad[x][y]);
			ans += to_string(quad[x][y + 1]);
			ans += to_string(quad[x + 1][y]);
			ans += to_string(quad[x + 1][y + 1]);
		}
		else {
			dfs(x, y, z);
			dfs(x, y + z, z);
			dfs(x + z, y, z);
			dfs(x + z, y + z, z);
		}
		ans += ")";
	}
	return;
}

int main() {
	int c = 0;
	scanf("%d", &N);
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			scanf("%1d", &quad[i][j]);
		}
	}
	dfs(0, 0, N);
	cout << ans;
	return 0;
}

www.acmicpc.net/problem/2583

처음엔 모눈종이가 거꾸로 되있고 좌표로 직사각형을 입력받아야해서 조금 생각을 해야했다.

하지만 그 후엔 그냥 단순히 DFS를 구현하면 되는 쉬운 문제였다.

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int m, n, k, cnt;
int map[101][101];
int visit[101][101];
vector<int> ans;
int dx[4] = { 0, 1, 0, -1 };
int dy[4] = { 1,0,-1,0 };

void dfs(int a, int b) {
	cnt++;
	for (int i = 0; i < 4; i++) {
		if (a + dx[i] >= 0 && a + dx[i] < n 
			&& b + dy[i] >= 0 && b +dy[i] < m
			&& visit[a + dx[i]][b + dy[i]] == 0 && map[a + dx[i]][b + dy[i]] == 0) {
			visit[a + dx[i]][b + dy[i]] = 1;
			dfs(a + dx[i], b + dy[i]);
		}
	}
	return;
}

int main() {
	int a, b, c, d;
	cin >> m >> n >> k;
	for (int i = 0; i < k; i++) {
		cin >> a >> b >> c >> d;
		for (int j = a; j < c; j++) {
			for (int k = b; k < d; k++) {
				map[j][k] = 1;
			}
		}
	}
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (visit[i][j] == 0 && map[i][j] == 0) {
				visit[i][j] = 1;
				cnt = 0;
				dfs(i, j);
				ans.push_back(cnt);
			}
		}
	}
	sort(ans.begin(), ans.end());
	cout << ans.size() << "\n";
	for (int i = 0; i < ans.size(); i++) {
		cout << ans[i] << " ";
	}
	return 0;
}