๋ฐฑ์ค€/Gold

[BOJ] 15685 : ๋“œ๋ž˜๊ณค ์ปค๋ธŒ

Jaeguk 2022. 5. 9. 23:07
๋ฌธ์ œ ๋งํฌ

15685๋ฒˆ: ๋“œ๋ž˜๊ณค ์ปค๋ธŒ (acmicpc.net)

 

15685๋ฒˆ: ๋“œ๋ž˜๊ณค ์ปค๋ธŒ

์ฒซ์งธ ์ค„์— ๋“œ๋ž˜๊ณค ์ปค๋ธŒ์˜ ๊ฐœ์ˆ˜ N(1 ≤ N ≤ 20)์ด ์ฃผ์–ด์ง„๋‹ค. ๋‘˜์งธ ์ค„๋ถ€ํ„ฐ N๊ฐœ์˜ ์ค„์—๋Š” ๋“œ๋ž˜๊ณค ์ปค๋ธŒ์˜ ์ •๋ณด๊ฐ€ ์ฃผ์–ด์ง„๋‹ค. ๋“œ๋ž˜๊ณค ์ปค๋ธŒ์˜ ์ •๋ณด๋Š” ๋„ค ์ •์ˆ˜ x, y, d, g๋กœ ์ด๋ฃจ์–ด์ ธ ์žˆ๋‹ค. x์™€ y๋Š” ๋“œ๋ž˜๊ณค ์ปค

www.acmicpc.net

๋‹จ์ˆœํ•œ ๊ตฌํ˜„ ๋ฌธ์ œ.

 

ํ’€์ด

ํ•œ ์ ์—์„œ ์‹œ์ž‘๋œ ์ปค๋ธŒ๋ฅผ ํ•œ ์„ธ๋Œ€๋งˆ๋‹ค ์‹œ๊ณ„๋ฐฉํ–ฅ์œผ๋กœ 90๋„ ํšŒ์ „ํ•˜์—ฌ ์ด์–ด๋ถ™์ธ ๋ชจ์–‘์„ ๋“œ๋ž˜๊ณค ์ปค๋ธŒ๋ผ๊ณ  ํ•œ๋‹ค.

๋‚˜๋Š” ํ•œ ์„ธ๋Œ€ ํ•œ ์„ธ๋Œ€ ์ง€๋‚ ๋•Œ๋งˆ๋‹ค ์ปค๋ธŒ๋ฅผ ๊ทธ๋ฆฌ๋Š” ๊ฒŒ์•„๋‹ˆ๋ผ g๋ฒˆ์งธ ์„ธ๋Œ€๊นŒ์ง€ ๊ทธ๋ ธ์„ ๋•Œ ์ปค๋ธŒ์˜ ๋ฐฉํ–ฅ์„ ๋ฒกํ„ฐ์— ์ €์žฅํ•ด๋‘๊ณ  ํ•œ๋ฒˆ์— ๊ทธ๋ฆฌ๋Š” ๋ฐฉ์‹์œผ๋กœ ์ง„ํ–‰ํ–ˆ๋‹ค.

์ฒ˜์Œ์— ์ปค๋ธŒ๋ฅผ ์ง์ ‘ ๊ทธ๋ ค๋ณด๋ฉด์„œ ๊ทœ์น™์„ ํŒŒ์•…ํ–ˆ๋‹ค.

์‹œ๊ณ„๋ฐฉํ–ฅ์œผ๋กœ 90๋„ ํšŒ์ „ํ•œ ํ›„ ์ปค๋ธŒ์˜ ์ง„ํ–‰๋ฐฉํ–ฅ์€ ์–ด๋–ป๊ฒŒ ๋ฐ”๋€Œ๋Š”์ง€ ์‚ดํŽด๋ณด๋ฉด

1. x์ขŒํ‘œ๊ฐ€ ์ฆ๊ฐ€ํ•˜๋Š” ๋ฐฉํ–ฅ (→) ์€ ํšŒ์ „ ํ›„ y์ขŒํ‘œ๊ฐ€ ๊ฐ์†Œํ•˜๋Š” ๋ฐฉํ–ฅ (↑) ์œผ๋กœ ๋ฐ”๋€๋‹ค.

2. y์ขŒํ‘œ๊ฐ€ ๊ฐ์†Œํ•˜๋Š” ๋ฐฉํ–ฅ (↑) ์€ ํšŒ์ „ ํ›„ x์ขŒํ‘œ๊ฐ€ ๊ฐ์†Œํ•˜๋Š” ๋ฐฉํ–ฅ (←) ์œผ๋กœ ๋ฐ”๋€๋‹ค.

3. x์ขŒํ‘œ๊ฐ€ ๊ฐ์†Œํ•˜๋Š” ๋ฐฉํ–ฅ (←) ์€ ํšŒ์ „ ํ›„ y์ขŒํ‘œ๊ฐ€ ์ฆ๊ฐ€ํ•˜๋Š” ๋ฐฉํ–ฅ (↓) ์œผ๋กœ ๋ฐ”๋€๋‹ค.

4. y์ขŒํ‘œ๊ฐ€ ์ฆ๊ฐ€ํ•˜๋Š” ๋ฐฉํ–ฅ (↓) ์€ ํšŒ์ „ ํ›„ x์ขŒํ‘œ๊ฐ€ ์ฆ๊ฐ€ํ•˜๋Š” ๋ฐฉํ–ฅ (→) ์œผ๋กœ ๋ฐ”๋€๋‹ค.

์ด ๊ทœ์น™์„ ์ด์šฉํ•ด์„œ g์„ธ๋Œ€ ๋“œ๋ž˜๊ณค ์ปค๋ธŒ๋ฅผ ์ด๋ฃจ๋Š” ์ง„ํ–‰๋ฐฉํ–ฅ์„ ์ˆœ์„œ๋Œ€๋กœ ๋ฒกํ„ฐ์— ์ €์žฅํ–ˆ๋‹ค.

๋‹จ, ๊ธฐ์กด์˜ ์ €์žฅ๋œ ๋ฐฉํ–ฅ์„ ํšŒ์ „ ํ›„์— ์ด์–ด๋ถ™์ด๋Š” ๊ฒƒ์ฒ˜๋Ÿผ ๊ตฌํ˜„ํ•˜๋ ค๋ฉด ๊ธฐ์กด์˜ ๋ฒกํ„ฐ์—์„œ ๋’ค์—์„œ ๋ถ€ํ„ฐ ๊ฐ’์„ ๊บผ๋‚ด ํšŒ์ „ํ•œ ํ›„๋ฒกํ„ฐ์— ์ถ”๊ฐ€ํ•ด์ฃผ์–ด์•ผ ํ•œ๋‹ค.

์˜ˆ๋ฅผ ๋“ค์–ด ์˜ˆ์‹œ์— ๋‚˜์˜จ 3์„ธ๋Œ€ ๋“œ๋ž˜๊ณค ์ปค๋ธŒ๋Š”

(0,0)์—์„œ ์‹œ์ž‘ํ•ด์„œ

→ ,↑, ,↑, ,, ← ,↑ ์ˆœ์„œ๋Œ€๋กœ ์ง„ํ–‰ํ•˜๋ฉด 3์„ธ๋Œ€ ๋“œ๋ž˜๊ณค ์ปค๋ธŒ๋ฅผ ๊ทธ๋ฆด ์ˆ˜ ์žˆ๋‹ค.

์ด ๋ฐฉํ–ฅ์„ ๋ฒกํ„ฐ์— ์ €์žฅํ•œ ํ›„ ํ•œ ๋ฒˆ์— ๊ทธ๋ ค์ฃผ์—ˆ๋‹ค. ๋ฒกํ„ฐ์— ์ €์žฅ๋œ ๋ฐฉํ–ฅ ์ˆœ์„œ๋Œ€๋กœ ์ด๋™ํ•˜๋ฉด์„œ ๋“œ๋ž˜๊ณค ์ปค๋ธŒ์— ํฌํ•จ๋˜๋Š” ์ขŒํ‘œ๋Š” visited๋ฐฐ์—ด์— true๋กœ ํ‘œ์‹œํ–ˆ๋‹ค.

 

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
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <string.h>
#include <string>
#include <stack>
#include <vector>
#include <math.h>
#include <queue>
#include <climits>
#include <algorithm>
#include <iomanip>
#include <map>
#define mod 998244353
using namespace std;
typedef long long ll;
typedef priority_queue<pair<intint>vector<pair<intint>>, greater<pair<intint>>> Priority_queue;
const int INF = INT_MAX;
const int MAX_N = 100 + 5;
bool Map[MAX_N][MAX_N];
int N;
 
int dx[] = { 1,0,-1,0 };
int dy[] = { 0,-1,0,1 };
 
void dragon_curve(int x, int y, int d, int g);
bool is_ans(int x, int y) {
    if (Map[x][y] && Map[x + 1][y] && Map[x][y + 1&& Map[x + 1][y + 1])
        return true;
    return false;
}
int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> N;
    for (int i = 0; i < N; i++) {
        int x, y, d, g;
        cin >> x >> y >> d >> g;
        dragon_curve(x, y, d, g);
    }
    int ans = 0;
    for (int i = 0; i < 100; i++) {
        for (int j = 0; j < 100; j++) {
            if (is_ans(i, j))
                ans++;
        }
    }
    cout << ans << "\n";
    return 0;
}
int change_direction(int d) {
    if (d == 0return 1;
    else if (d == 1return 2;
    else if (d == 2return 3;
    else if (d == 3return 0;
}
void dragon_curve(int x, int y, int d, int g) {
    vector<int> direction;
    direction.push_back(d);
    for (int i = 1; i <= g; i++) { //generation
        for (int j = direction.size() - 1; j >= 0; j--) {
            direction.push_back(change_direction(direction[j]));
        }
    }
    Map[x][y] = true;
    for (int i = 0; i < direction.size(); i++) {
        x += dx[direction[i]];
        y += dy[direction[i]];
        Map[x][y] = true;
    }
}
cs

๊ทธ๋ฆฌ๊ณ  ๋งŒ์•ฝ ํ•œ ๋ณ€์˜ ๊ธธ์ด๊ฐ€ 1์ธ ์ •์‚ฌ๊ฐํ˜• ๋„ค ๊ผญ์ง€์ ์ด ๋ชจ๋‘ true๋กœ ํ‘œ์‹œ๋˜์–ด์žˆ์œผ๋ฉด ๊ทธ ์ •์‚ฌ๊ฐํ˜•์€ ๋“œ๋ž˜๊ณค ์ปค๋ธŒ์— ํฌํ•จ๋œ ๊ฒƒ์œผ๋กœ ์ธ์ง€ํ–ˆ๋‹ค.

728x90