Hilbert Curve
๋ ์ ์์ขํ๊ณ์์ ์ฌ์ฉ๊ฐ๋ฅํ ์ผ์ข
์ Space-Filling Curve
์ด๋ค. 1์ฐจ์ ์ขํ๊ณ์์ ์ด๋ค ์ขํ ๋ฆฌ์คํธ๊ฐ ์์ด์ ๊ทธ๋ค์ ์ต๋จ ๊ฒฝ๋ก๋ก ๋ฐฉ๋ฌธํด์ผ ํ๋ค๊ณ ํ๋ค๋ฉด ์ด๋ฅผ ๊ตฌํ๋ ๊ฒ์ ๊ฐ๋จํ๋ค. ์์น๋ฅผ ์ ๋ ฌํด์ ์ค๋ฆ์ฐจ์์ด๋ ๋ด๋ฆผ์ฐจ์์ผ๋ก ๋ฐฉ๋ฌธํ๋ฉด ๋๋ค. 2์ฐจ์ ์ขํ๊ณ๊ฐ ๋๋ฉด ์ด์ผ๊ธฐ๊ฐ ๋ง์ด ๋ณต์กํด์ง๋ค. ์ด๋ฅผ Hilbert Curve
๋ฅผ ์ฌ์ฉํด์ 1์ฐจ์ ์ขํ๊ณ์ฒ๋ผ 2์ฐจ์ ์ขํ๊ณ๋ฅผ projection
ํ ์ ์๊ณ , ํด๋ฆฌ์คํฑํ๊ฒ ์ด๋์ ๋ ๊ฐ๊น์ด ์ ๋ค๋ผ๋ฆฌ ๋ฐฉ๋ฌธํ ์ ์๊ฒ ๋๋ค.
์๋ ์ฝ๋๋ ์๋์ codeforces blog์์ ๊ณต์ ๋ ์ฝ๋๋ก, ์์์ , ์ขํ๊ฐ ์ฃผ์ด์ก์ ๋์ Hilbert Curve ์์ ์์๋ฅผ ์๊ฐ ๋ณต์ก๋๋ก ๊ตฌํ ์ ์๋ค.
constexpr int rotateDelta[4] = {3, 0, 0, 1};inline int64_t hilbertOrder(int x, int y, int pow, int rotate) {if (pow == 0) {return 0;}int hpow = 1 << (pow-1);int seg = (x < hpow) ? ((y < hpow) ? 0 : 3) : ((y < hpow) ? 1 : 2);seg = (seg + rotate) & 3;int nx = x & (x ^ hpow), ny = y & (y ^ hpow);int nrot = (rotate + rotateDelta[seg]) & 3;int64_t subSquareSize = int64_t(1) << (2*pow - 2);int64_t ans = seg * subSquareSize;int64_t add = hilbertOrder(nx, ny, pow-1, nrot);ans += (seg == 1 || seg == 2) ? add : (subSquareSize - add - 1);return ans;}
Mo's
์๊ณ ๋ฆฌ์ฆ์ ๊ฒฝ์ฐ ์ฟผ๋ฆฌ ๋ฌธ์ ์์ ์ฟผ๋ฆฌ์ , ๊ธฐ์ค์ผ๋ก ์ ๋ ฌํด์ ๋์ํ๋ ์๊ณ ๋ฆฌ์ฆ์ด๋ค. ์ด์ ๊ดํด์๋ ๊ธ ์๋์ ์๋ ๋ธ๋ก๊ทธ์ ์ ์ ๋ฆฌ๋์ด ์๋ค. ๊ณผ ๊ฐ ๊ฑฐ์ ์ ์ฌํ ๋ฌธ์ ์์๋ Mo's
์๊ณ ๋ฆฌ์ฆ์ zigzag
์์ด๋์ด๋ฅผ ์์ ๊ฒ๊ณผ Hilbert Curve
๋ฅผ ํ์ฉํ ๋ฐฉ์์ด ๊ฑฐ์ ์ ์ฌํ ์ฑ๋ฅ์ ๋ณด์ธ๋ค. ์์ด๊ณผ ์ฟผ๋ฆฌ 0
๋ฌธ์ ์์ ์ธก์ ํ ์๋๋ ์๋์ ๊ฐ๋ค.
Mo's
: 1070 msMo's
+ zigzag
: 680 msMo's
+ Hilbert
: 660 ms์ฑ๋ฅ์ ์ํ๋ TSP
๋ฌธ์ ์์ ํ์ฉ ๊ฐ๋ฅํ๋ค. ์์์ ์ขํ๋ฅผ ๋น์ฉ์ ์ต์๋ก ํด์ ๋ฐฉ๋ฌธํด์ผ ํ ๋, ์์์ ์ดํด๋ณธ ๊ฒ์ฒ๋ผ 2์ฐจ์ ์ขํ๊ณ๋ฅผ 1์ฐจ์ ์ขํ๊ณ์ธ ๊ฒ์ฒ๋ผ ์์๋ฅผ ์ ํด์ ๋ฐฉ๋ฌธํ ์ ์๋ค. ๋์ถฉ int map[1000][1000]
์ ๋๊น์ง๋ ๋ฏธ๋ฆฌ ์์๋ฅผ ์ ์ฅํด๋๊ณ ์ ๊ตฌํ๋ ๊ฒ์ด ์ข์ ๋ฐฉ์์ผ๋ก ๋ณด์ธ๋ค. ์ด์ ์ ๋ค๋ค๋ Angle Sort
์์ ์ฑ๋ฅ ๋น๊ต๋ ์ดํ์ ์งํํด๋ด์ผ๊ฒ ๋ค.
// [TODO] 2์ฐจ์ ๊ณต๊ฐ์ Hilbert Curve ๋ฐฉ๋ฌธ ์์๋ฅผ ์ฑ์ฐ๋ ์ฝ๋