[G4] 백준 17092번 색칠 공부 C++ 해시맵

리뷰

 

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

어음.. 풀긴했는데 이게 맞나 싶다.

 

 

전역 변수

• n, m : 맵의 세로/가로 크기를 저장할 변수
• q : 검정색 칸의 개수를 저장할 변수
• dic : 검정색 칸의 개수가 0~9개인 부분 모눈종이의 개수를 저장할 해시맵
• lst : 맵 정보를 저장할 2차원 해시맵

 

함수

없음

 

 

문제풀이

1. n, m, q값을 입력 받고, dic의 0의 값을 (n - 2) * (m - 2)로 초기화 해준다.
2. dic의 key 1 ~ 9의 value를 0으로 초기화 해준다.
3. q번의 while 루프를 수행하고, 매 루프마다 검은색 칸의 좌표를 입력 받아준다.
4. lst의 x, y좌표에 해당하는 값을 1로 저장해 준다.
5. x, y좌표에서 주변 9칸의 3 * 3크기의 모눈종이를 순회하며 검은칸의 개수를 변수 cnt에 저장한다.
6. dic의 cnt - 1키의 값을 감소시키고, cnt키의 값을 증가시킨다.
7. 벡터 ans를 크기 10으로 초기화 하고, 해시맵의 키를 ans의 인덱스로 해시맵의 값을 ans의 값으로 저장한다.
8. ans에 저장된 값을 줄바꿈을 기준으로 순차적으로 출력해 준다.

 

트러블 슈팅

없음

 

 

참고 사항

• 같은 칸이 여러 번 주어지는 경우는 없다.
• 방금 검은색으로 칠한 칸의 주변을 순회할 때 맵의 범위를 벗어나면 안된다.
• 메모리와 시간이 생각보다 많이 소모되어 최적해는 아닌듯 싶다.

 

정답 코드

#include<iostream>
#include<unordered_map>
#include<vector>
#define ll long long
using namespace std;

ll n, m, q;
unordered_map<int, ll> dic;
unordered_map<int, unordered_map<int, int>> lst;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> n >> m >> q;
	dic[0] = (n - 2) * (m - 2);
	for (int i = 1; i < 10; ++i) dic[i] = 0;

	while (q--) {
		int x, y; cin >> x >> y;
		lst[x][y] = 1;
		for (int i = x - 2; i <= x; ++i) {
			if (1 <= i && i + 2 <= n) {
				for (int j = y - 2; j <= y; ++j) {
					if (1 <= j && j + 2 <= m) {
						int cnt = 0;
						for (int ii = i; ii <= i + 2; ++ii) {
							for (int jj = j; jj <= j + 2; ++jj) {
								if (lst[ii][jj]) cnt++;
							}
						}
						dic[cnt - 1]--;
						dic[cnt]++;
					}
				}
			}
		}
	}
	vector<ll> ans(10);
	for (const auto& i : dic) ans[i.first] = i.second;
	for (ll i : ans) cout << i << "\n";
}