https://www.acmicpc.net/problem/29721
문제 난이도는 쉬운 편이지만 cpp의 unordered_set에 대해 새롭게 알게된 부분이 있어서 정리해봅니다.
문제는 체스판 위에 놓여져 있는 다바바를 이동시킬 수 있는 칸이 몇 개인지 세기만 하면 됩니다.
다바바는 상하좌우로 2칸만 이동할 수 있으며 나이트처럼 경로에 위치한 다른 기물을 뛰어 넘을 수 있습니다.
체스판의 크기가 10만이므로 배열로는 해결할 수 없습니다.
set과 unordered_set 둘다 사용이 가능했지만 정렬이 필요없기에 unordered_set을 사용했습니다.
문제 로직은 간단합니다.
다바바는 맵 밖이나 다른 다바바가 위치한 좌표에는 갈 수 없으니 최초 다바바의 위치는 set에 미리 넣어둡니다.
이후에 상하좌우로 2칸씩 이동시켜서 set에 insert하고, 그 횟수를 구하면 됩니다.
확실히 메모리와 시간이 줄어드는 것을 확인할 수 있습니다.
저는 처음에는 set을 활용하여 문제를 풀었고, 시간을 줄이기 위해 unordered_set으로 바꾸는 도중에 컴파일 에러가 떴는데
unordered_set은 key를 해시화해서 사용하는데 pair에 대한 기본 해시 함수가 없기 때문에 발생한 에러였고, 해시 함수를 직접 정의를 해야했습니다.
|
1
2
3
4
5
|
struct pair_hash {
size_t operator()(const pii& p) const {
return hash<int>()(p.first) ^ hash<int>()(p.second);
}
};
|
cs |
이런식으로 해시 함수를 직접 정의할 수 있습니다.
다만 이렇게 둔다면 p.first와 p.second가 비슷한 값이면 해시 충돌이 많이 발생한다고 합니다.
특히 이 문제에서는 상하좌우로 2칸씩만 이동하기 때문에 치명적인 문제가 될 수 있겠다는 생각이 들었습니다.
역시나 TLE가 떴습니다.
p.first나 p.second 둘 중 하나에 소수를 곱해준다면 충돌 확률을 낮추는 효과를 가져올 수 있습니다.
다만 너무 큰 숫자를 곱하게 되면 곱셈 연산에 소요되는 시간이 더 많이 발생할 수 있으니 적당한 수를 곱하는게 좋아보입니다.
그리고 양쪽 모두 소수를 곱하는 방법도 있는데 충돌은 줄어들겠지만 그만큼 곱셈 연산이 더 늘어나서 시간이 더 소요될 수 있습니다.
|
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
|
#include <iostream>
#include <vector>
#include <unordered_set>
#define MAX 100001
using namespace std;
typedef pair<int, int> pii;
struct pair_hash {
size_t operator()(const pii& p) const {
return hash<int>()(p.first) ^ (hash<int>()(p.second) * 31);
}
};
unordered_set<pii, pair_hash> s;
vector<pii> v;
int direct[4][2] = { {2,0},{0,2},{-2,0},{0,-2} };
int N, K;
void func() {
int ret = 0;
for (auto xy : v) {
int x = xy.first;
int y = xy.second;
for (int d = 0; d < 4; d++) {
int nx = x + direct[d][0];
int ny = y + direct[d][1];
if (nx <= 0 || ny <= 0 || nx > N || ny > N) continue;
if (s.find({ nx,ny }) != s.end()) continue;
ret++;
s.insert({ nx,ny });
}
}
cout << ret << '\n';
}
void input() {
int x, y;
cin >> N >> K;
for (int i = 0; i < K; i++) {
cin >> x >> y;
v.push_back({ x,y });
s.insert({ x,y });
}
}
int main() {
cin.tie(NULL); cout.tie(NULL);
ios::sync_with_stdio(false);
input();
func();
return 0;
}
|
cs |
'algorithm > data-structure' 카테고리의 다른 글
| boj 15926 현욱은 괄호왕이야!! (1) | 2023.07.24 |
|---|---|
| boj 21939 문제 추천 시스템 Version 1 (0) | 2022.02.11 |
| boj 17299 오등큰수 (0) | 2021.02.22 |
| boj 9372 상근이의 여행 (0) | 2021.02.09 |
| boj 1158 요세푸스 문제 (0) | 2021.02.09 |