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

 

5373번: 큐빙

각 테스트 케이스에 대해서 큐브를 모두 돌린 후의 윗 면의 색상을 출력한다. 첫 번째 줄에는 뒷 면과 접하는 칸의 색을 출력하고, 두 번째, 세 번째 줄은 순서대로 출력하면 된다. 흰색은 w, 노란

www.acmicpc.net

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
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <utility>
#include <unordered_map>
#include <map>
#include <queue>
#include <stack>
#include <iomanip>
using namespace std;
void init() {
    ios::sync_with_stdio(false);
    cin.tie(0);
}
int T; // TEST_CASE
int n; // 돌린 횟수
/*
W 위 G 왼쪽 R 앞면 Y 아래면 B 오른쪽면 왼쪽 초록색
      O O O
      O O O
      O O O
G G G Y Y Y B B B W W W
G G G Y Y Y B B B W W W
G G G Y Y Y B B B W W W
      R R R
      R R R
      R R R
 
         1  2  3
         4  5  6
         7  8  9
10 11 12 19 20 21 28 29 30 37 38 39
13 14 15 22 23 24 31 32 33 40 41 42
16 17 18 25 26 27 34 35 36 43 44 45
         46 47 48
         49 50 51
         52 53 54
*/
// 0 L, 1 R, 2 U, 3 D, 4 F, 5 B
int oper[6][12] = {
    {39,42,45,52,49,46,25,22,19,7 ,4 ,1 },
    {43,40,37,3 ,6 ,9 ,21,24,27,48,51,54},
    {30,33,36,54,53,52,16,13,10,1 ,2 ,3 },
    {34,31,28,9 ,8 ,7 ,12,15,18,46,47,48},
    {45,44,43,36,35,34,27,26,25,18,17,16},
    {10,11,12,19,20,21,28,29,30,37,38,39}
};
int cube[6][3][3] = {
    {{10,13,16},{11,14,17},{12,15,18}},
    {{36,33,30},{35,32,29},{34,31,28}},
    {{39,38,37},{42,41,40},{45,44,43}},
    {{21,20,19},{24,23,22},{27,26,25}},
    {{52,53,54},{49,50,51},{46,47,48}},
    {{3 ,2 ,1 },{6 ,5 ,4 },{9 ,8 ,7}}
};
char MAP_init[55] = { 0,
'o','o','o','o','o','o','o','o','o',
'g','g','g','g','g','g','g','g','g',
'y','y','y','y','y','y','y','y','y',
'b','b','b','b','b','b','b','b','b',
'w','w','w','w','w','w','w','w','w',
'r','r','r','r','r','r','r','r','r'
};
char MAP_COPY[55];
void turn(const string& op) {
    int num_oper;
    if (op[0] == 'L')
        num_oper = 0;
    else if (op[0] == 'R')
        num_oper = 1;
    else if (op[0] == 'U')
        num_oper = 2;
    else if (op[0] == 'D')
        num_oper = 3;
    else if (op[0] == 'F')
        num_oper = 4;
    else if (op[0] == 'B')
        num_oper = 5;
    deque<char> index;
    deque<char> cube_front[3];
    for (const auto& i : oper[num_oper]) 
        index.push_back(MAP_COPY[i]);
    if (op[1] == '+') {
        for (int i = 0; i < 3; i++) {
            index.push_front(index.back());
            index.pop_back();
        }
        for (int j = 0; j <= 2; j++) {
            for (int i = 2; i >= 0; i--) {
                cube_front[j].push_back(MAP_COPY[cube[num_oper][i][j]]);
            }
        }
    }
    else {
        for (int i = 0; i < 3; i++) {
            index.push_back(index.front());
            index.pop_front();
        }
        int count = 0;
        for (int j = 2; j >= 0; j--) {
            for (int i = 0; i <=2; i++) {
                cube_front[count].push_back(MAP_COPY[cube[num_oper][i][j]]);
            }
            count++;
        }
    }
    for (const auto& i : oper[num_oper]) {
        MAP_COPY[i] = index.front();
        index.pop_front();
    }
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) {
            MAP_COPY[cube[num_oper][i][j]] = cube_front[i][j];
            
        }
    }
}
void print() {
    cout << MAP_COPY[39] << MAP_COPY[38] << MAP_COPY[37] << "\n";
    cout << MAP_COPY[42] << MAP_COPY[41] << MAP_COPY[40] << "\n";
    cout << MAP_COPY[45] << MAP_COPY[44] << MAP_COPY[43] << "\n";
}
void solve() {
    cin >> T;
    while (T--) {
        memcpy(MAP_COPY, MAP_init, sizeof(MAP_init));
        cin >> n;
        while (n--) {
            string oper;
            cin >> oper;
            turn(oper);
        }
        print();
    }
}
int main() {
    init();
    solve();
}
 
 cs

'BAEKJOON ONLINE JUDGE' 카테고리의 다른 글

[백준 16939] 2x2x2 큐브 (C++)  (0) 2021.09.01
[백준 17406] 배열 돌리기 4 (C++)  (0) 2021.08.30
[백준 17779] 게리맨더링 2 (C++)  (0) 2021.08.29
[백준 1946] 신입 사원 (C++)  (0) 2021.08.28
[백준 1715] 카드 정렬하기 (C++)  (0) 2021.08.27

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

 

21609번: 상어 중학교

상어 중학교의 코딩 동아리에서 게임을 만들었다. 이 게임은 크기가 N×N인 격자에서 진행되고, 초기에 격자의 모든 칸에는 블록이 하나씩 들어있고, 블록은 검은색 블록, 무지개 블록, 일반 블록

www.acmicpc.net

상당히 더러웠던 문제.

문제 자체는 어렵지 않다. 하지만 시키는게 많다, 터트리고, 중력, 돌리고, 중력...

코드의 흐름은 다음과 같다.

 

init() 에서는 빠른 입력을 위한 것

 

input() 도 그냥 입력 받는다. 딱히 특별한게 없다.


solve() 함수 에서 부터 문제 풀이를 시작한다.


find_block_group()을 돌린다, 이 함수는 false가 return되면 오토플레이가 끝나게 해놨다.
find_block_group에서는 블록그룹을 찾고, 터트려야하는 것을 판별, 그다음은 터트리는 것 까지 구현했다.

우선 memset을 이용해 check 함수, 즉 방문여부를 확인 하는 것을 false로 초기화 하였다.
맵 크기가 21*21이라 크지 않아서 해도 시간초과에 상관없을거같다.
이중 포문과 bfs를 통해서 블록 그룹을 찾는다. 이때 0도아니고, -1도 아니고 -2(빈칸)도 아니여야 한다.
그리고 check배열이 false여야 한다.

1
2
3
4
5
6
7
8
struct block {
    deque<pair<int, int>> Rainbow_block;
    deque<pair<int, int>> Base_block;
    int total_size;
    int base_block_x;
    int base_block_y;
    int base_color;
};
 cs

이때 다음과 같은 block 그룹 함수를 사용 했다. 블럭의 색, 기준블럭의 좌표, 무지개랑 기준블럭을 저장하는 deque.
그 다음에는 bfs로 탐색한다. base_color가 같은것, 그리고 무지개 블록, bfs는 다음과 같다.

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
void bfs(const int& i, const int& j) {
    block temp;
    queue<pair<int, int>> q;
    // 색깔지정 및 탐색 준비
    temp.base_color = MAP[i][j];
    temp.total_size = 0;
    temp.base_block_x = i;
    temp.base_block_y = j;
    check[i][j] = true;
    q.push(make_pair(i, j));
    // 베이스 블럭이 당연히 맨 처음시작하는 곳 아닌가? 라고 생각
    // 위에서 부터 시작하니
    // 탐색 시작
    while (!q.empty()) {
        int x = q.front().first;
        int y = q.front().second;
        q.pop();
        if (MAP[x][y] == temp.base_color) {
            temp.Base_block.push_back(make_pair(x, y));
            temp.total_size++;
        }
        else if (MAP[x][y] == 0) {
            temp.Rainbow_block.push_back(make_pair(x, y));
            temp.total_size++;
        }
        for (int index = 0; index < 4; index++) {
            int next_x = x + dx[index];
            int next_y = y + dy[index];
            if (check_range(next_x, next_y) && check[next_x][next_y] == false) {
                if (MAP[next_x][next_y] == temp.base_color || MAP[next_x][next_y] == 0) {
                    check[next_x][next_y] = true;
                    q.push(make_pair(next_x, next_y));
                }
            }
        }
    }
    // 탐색 종료 후 정리
    for (auto i : temp.Rainbow_block)
        check[i.first][i.second] = false;
    if (temp.total_size < 2)
        return;
    block_group.push_back(temp);
}
 cs

평범한 bfs지만, 색블럭 저장, 무지개 블럭 저장하는 과정만 추가. 그리고 탐색이 끝난 뒤에는 다음과 같이 
check 배열에서 rainbow_block들은 다시 false로 처리 해야한다. 왜냐하면 다른 블록 그룹도 무지개 블록을 가질 수 
있기때문이다.
그리고 만약 size가 2보다 작으면 그냥 return, 문제조건이다,
block_group에 push_back해준다.
이 과정을 거치면 모든  block_group을 찾을 수 있다. 그러면 문제의 조건에 맞춰서  터트릴 block을 선정해야한다.
나는 정렬을 사용했다 . 다음과 같은 cmp함수를 만들었다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
bool cmp(const block& x, const block& y) {
    if (x.total_size != y.total_size)
        return x.total_size > y.total_size;
    else {
        if (x.Rainbow_block.size() != y.Rainbow_block.size())
            return x.Rainbow_block.size() > y.Rainbow_block.size();
        else {
            if (x.base_block_x != y.base_block_x)
                return x.base_block_x > y.base_block_x;
            else
                return x.base_block_y > y.base_block_y;
        }
    }
}
 cs

뭐 그냥 그렇다. 처음 조건 size가 큰것, 그 다음은 무지개 블럭 사이즈가 큰거, 그 다음은 기준블럭의 행, 그 다음은 기준블럭의 열.
그러면 터트려야 하는 것이 0번 인덱스로 온다.
그리고 나면 뭐 deque에 있는 터트리는 블럭 좌표를 pop하고, 더해주면 끝이다.
그 다음은 중력,
중력은 별거없다. 맨 아래줄부터 아래가 뭔지 check하면서 내려오면된다. 
반시계방향도 별거 없다. 기존에 1열이 -> 5행, 2열 ->4행,... 5열->1행으로 가는 것만 알면된다.
그리고 코드를 반복하면 끝이다. 전체코드는 다음과 같다.

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
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
// 백준 21609 상어 중학교
#include <iostream>
#include <queue>
#include <deque>
#include <utility>
#include <iomanip>
#include <cstring>
#include <algorithm>
#define MAX 20+1
using namespace std;
struct block {
    deque<pair<int, int>> Rainbow_block;
    deque<pair<int, int>> Base_block;
    int total_size;
    int base_block_x;
    int base_block_y;
    int base_color;
};
int dx[4] = { 0,1,0,-1 };
int dy[4] = { 1,0,-1,0 };
int N, M;
int MAP[MAX][MAX];
bool check[MAX][MAX] = { false };
deque<block> block_group;
int result_point = 0;
void reverse_clock_wise() {
    // 시계방향으로 돌리면 1열 2열 3열 4열 5열 -> 5행 4행 3행 2행 1행
    queue<int> q;
    for (int j = 1; j <= N; j++)
        for (int i = 1; i <= N; i++)
            q.push(MAP[i][j]);
    for (int i = N; i >= 1; i--) {
        for (int j = 1; j <= N; j++) {
            MAP[i][j] = q.front();
            q.pop();
        }
    }
}
void Gravity() {
    // 내려가는 방향은 1번 인덱스
    for (int i = N - 1; i >= 1; i--) {
        for (int j = 1; j <= N; j++) {
            if (MAP[i][j] == -1 || MAP[i][j] == -2)
                continue;
            int num = MAP[i][j];
            MAP[i][j] = -2;
            int prev_x = i;
            prev_x++;
            while (prev_x <= N) {
                if (MAP[prev_x][j] != -2)
                    break;
                prev_x++;
            }
            prev_x--;
            MAP[prev_x][j] = num;
        }
    }
}
bool cmp(const block& x, const block& y) {
    if (x.total_size != y.total_size)
        return x.total_size > y.total_size;
    else {
        if (x.Rainbow_block.size() != y.Rainbow_block.size())
            return x.Rainbow_block.size() > y.Rainbow_block.size();
        else {
            if (x.base_block_x != y.base_block_x)
                return x.base_block_x > y.base_block_x;
            else
                return x.base_block_y > y.base_block_y;
        }
    }
}
bool check_range(const int& next_x, const int& next_y) {
    if (next_x >= 1 && next_y >= 1 && next_x <= N && next_y <= N)
        return true;
    else
        return false;
}
void bfs(const int& i, const int& j) {
    block temp;
    queue<pair<int, int>> q;
    // 색깔지정 및 탐색 준비
    temp.base_color = MAP[i][j];
    temp.total_size = 0;
    temp.base_block_x = i;
    temp.base_block_y = j;
    check[i][j] = true;
    q.push(make_pair(i, j));
    // 베이스 블럭이 당연히 맨 처음시작하는 곳 아닌가? 라고 생각
    // 위에서 부터 시작하니
    // 탐색 시작
    while (!q.empty()) {
        int x = q.front().first;
        int y = q.front().second;
        q.pop();
        if (MAP[x][y] == temp.base_color) {
            temp.Base_block.push_back(make_pair(x, y));
            temp.total_size++;
        }
        else if (MAP[x][y] == 0) {
            temp.Rainbow_block.push_back(make_pair(x, y));
            temp.total_size++;
        }
        for (int index = 0; index < 4; index++) {
            int next_x = x + dx[index];
            int next_y = y + dy[index];
            if (check_range(next_x, next_y) && check[next_x][next_y] == false) {
                if (MAP[next_x][next_y] == temp.base_color || MAP[next_x][next_y] == 0) {
                    check[next_x][next_y] = true;
                    q.push(make_pair(next_x, next_y));
                }
            }
        }
    }
    // 탐색 종료 후 정리
    for (auto i : temp.Rainbow_block)
        check[i.first][i.second] = false;
    if (temp.total_size < 2)
        return;
    block_group.push_back(temp);
}
bool find_block_group() {
    // 블록 그룹 먼저 찾기
    memset(check, false, sizeof(check));
    for (int i = 1; i <= N; i++)
        for (int j = 1; j <= N; j++)
            if (MAP[i][j] != 0 && MAP[i][j] != -1 && MAP[i][j] != -2 && check[i][j] == false)
                bfs(i, j);
    if (block_group.empty())
        return false;
    sort(block_group.begin(), block_group.end(), cmp);
    // block 터트리기 -2 는 빈칸
    result_point += block_group[0].total_size * block_group[0].total_size;
    for (auto i : block_group[0].Rainbow_block)
        MAP[i.first][i.second] = -2;
    for (auto i : block_group[0].Base_block)
        MAP[i.first][i.second] = -2;
    block_group.clear();
    return true;
}
void solve() {
    for (;;) {
        if (find_block_group() == false)
            return;
        Gravity();
        reverse_clock_wise();
        Gravity();
    }
}
void input() {
    cin >> N >> M;
    // (-1,검은색),(0,무지개),그리고 나머지 M까지 색
    for (int i = 1; i <= N; i++)
        for (int j = 1; j <= N; j++)
            cin >> MAP[i][j];
}
void init() {
    ios::sync_with_stdio(false);
    cin.tie(0);
}
int main() {
    init();
    input();
    solve();
    cout << result_point << endl;
}
 cs

'BAEKJOON ONLINE JUDGE' 카테고리의 다른 글

[백준 21611] 마법사 상어와 블리자드 (C++)  (0) 2021.08.26
[백준 20061] 모노미노도미노 2 (C++)  (0) 2021.08.23
[백준 14499] 주사위 굴리기 (C++)  (0) 2021.08.21
[백준 3190] 뱀 (C++)  (0) 2021.08.21
[백준 1092] 배 (C++)  (0) 2021.08.21

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

 

14499번: 주사위 굴리기

첫째 줄에 지도의 세로 크기 N, 가로 크기 M (1 ≤ N, M ≤ 20), 주사위를 놓은 곳의 좌표 x y(0 ≤ x ≤ N-1, 0 ≤ y ≤ M-1), 그리고 명령의 개수 K (1 ≤ K ≤ 1,000)가 주어진다. 둘째 줄부터 N개의 줄에 지도

www.acmicpc.net

사실 주사위가 이동하는 거만 잘 처리하면 쉬운문제이다.

그거빼고 할게없는 문제.

코드의 대부분이 주사위를 굴린 뒤의 상태이니 말 다했다.

면을 복사하는것과 출력은 매우쉽다.

 

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
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
#include <iostream>
using namespace std;
int N, M, x, y, K;
int MAP[20][20];
int oper[1001];
int num_dice[7] = { 0, 0,0,0,0,0,0 };
// 1    2    3        4    5      6 
// 윗면 앞면 오른쪽면 뒷면 왼쪽면 바닥면
int dice[7]={ 0,1,5,3,2,4,6 };
int dx[5] = { 0, 0,0,-1,1 };
int dy[5] = { 0, 1,-1,0,0 };
void oper_1() {
    int temp1 = dice[1]; // 윗면
    int temp2 = dice[3]; // 오른쪽면
    int temp3 = dice[5]; // 왼쪽면
    int temp4 = dice[6]; // 바닥면
    dice[1] = temp3;
    dice[3] = temp1;
    dice[5] = temp4;
    dice[6] = temp2;
}
void oper_2() {
    int temp1 = dice[1]; // 윗면
    int temp2 = dice[3]; // 오른쪽면
    int temp3 = dice[5]; // 왼쪽면
    int temp4 = dice[6]; // 바닥면
    dice[1] = temp2;
    dice[3] = temp4;
    dice[5] = temp1;
    dice[6] = temp3;
}
void oper_3() {
    int temp1 = dice[1]; // 위
    int temp2 = dice[2]; // 앞
    int temp3 = dice[6]; // 바닥
    int temp4 = dice[4]; // 뒷면
    dice[1] = temp2;
    dice[2] = temp3;
    dice[6] = temp4;
    dice[4] = temp1;
}
void oper_4() {
    int temp1 = dice[1]; // 위
    int temp2 = dice[2]; // 앞
    int temp3 = dice[6]; // 바닥
    int temp4 = dice[4]; // 뒷면
    dice[1] = temp4;
    dice[2] = temp1;
    dice[6] = temp2;
    dice[4] = temp3;
}
void find() {
    for (int i = 1; i <= K; i++) {
        int next_x = x + dx[oper[i]];
        int next_y = y + dy[oper[i]];
        if (next_x >= 0 && next_x <= N - 1 && next_y >= 0 && next_y <= M - 1) {
            //cout << "oper : "<< oper[i] << endl;
            if (oper[i] == 1)
                oper_1();
            else if (oper[i] == 2)
                oper_2();
            else if (oper[i] == 3)
                oper_3();
            else if (oper[i] == 4)
                oper_4();
            if (MAP[next_x][next_y] == 0) {
                MAP[next_x][next_y] = num_dice[dice[6]];
                cout << num_dice[dice[1]] << "\n";
            }
            else {
                num_dice[dice[6]] = MAP[next_x][next_y];
                MAP[next_x][next_y] = 0;
                cout << num_dice[dice[1]] << "\n";
            }
            x = next_x;
            y = next_y;
        }
        else
            continue;
    }
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> N >> M;
    cin >> x >> y >> K;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            cin >> MAP[i][j];
        }
    }
    for (int i = 1; i <= K; i++)
        cin >> oper[i];
 
    find();
}
cs

'BAEKJOON ONLINE JUDGE' 카테고리의 다른 글

[백준 20061] 모노미노도미노 2 (C++)  (0) 2021.08.23
[백준 21609] 상어 중학교 (C++)  (0) 2021.08.22
[백준 3190] 뱀 (C++)  (0) 2021.08.21
[백준 1092] 배 (C++)  (0) 2021.08.21
[백준 19237] 어른 상어 (C++)  (0) 2021.08.21

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

 

3190번: 뱀

 'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다. 게임

www.acmicpc.net

옛날에 풀었던 문제이다.

뱀의 상태만 잘 처리하면 쉬운문제이다.

풀이는 다음과 같다.

snake의 좌표는 queue로 관리한다.

사실 queue로 뱀의 좌표를 관리하면 쉬운문제이다.

코드는 다음과 같다.

 

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
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
#include <iostream>
#include <vector>
#include <utility>
#include <queue>
#define MAX 100+1
using namespace std;
int N,K,L;
int map[MAX][MAX];
vector<pair<int, char>> vec;
queue<pair<int, int>> snake;
// 오른쪽 아래 왼쪽 위
int dx[4] = { 0,1,0,-1 };
int dy[4] = { 1,0,-1,0 };
void find() {
    int state = 0;
    int x = 1;
    int y = 1;
    map[x][y] = 1;
    int time = 0;
    int index = 0;
    snake.push(make_pair(x, y));
    while (1) {
        if (!vec.empty() && time == vec[index].first) {
            if (vec[index].second == 'L') {
                state = state - 1;
                if (state == -1) {
                    state = 3;
                }
            }
            if (vec[index].second == 'D') {
                state = state + 1;
                if (state == 4) {
                    state = 0;
                }
            }
            vec.erase(vec.begin());
        }
        time++;
        int next_x = x + dx[state];
        int next_y = y + dy[state];
        if (next_x >= 1 && next_x <= N && next_y >= 1 && next_y <= N) {
            if (map[next_x][next_y] == 0) {
                map[next_x][next_y] = 1;
                map[snake.front().first][snake.front().second] = 0;
                snake.pop();
                snake.push(make_pair(next_x, next_y));
                x = next_x;
                y = next_y;
            }
            else if (map[next_x][next_y] == 1)
                break;
            else if (map[next_x][next_y] == 2) {
                snake.push(make_pair(next_x, next_y));
                map[next_x][next_y] = 1;
                x = next_x;
                y = next_y;
            }
        }
        else
            break;
    }
    cout << time << endl;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> N;
    cin >> K;
    for (int i = 0; i < K; i++) {
        int x, y;
        cin >> x >> y;
        map[x][y] = 2;
    }
    cin >> L;
    for (int i = 0; i < L; i++) {
        int x;
        char y;
        cin >> x >> y;
        vec.push_back(make_pair(x, y));
    }
    find();
}
cs

'BAEKJOON ONLINE JUDGE' 카테고리의 다른 글

[백준 21609] 상어 중학교 (C++)  (0) 2021.08.22
[백준 14499] 주사위 굴리기 (C++)  (0) 2021.08.21
[백준 1092] 배 (C++)  (0) 2021.08.21
[백준 19237] 어른 상어 (C++)  (0) 2021.08.21
[백준 17090] 미로 탈출하기 (C++)  (0) 2021.08.20

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

 

1092번: 배

첫째 줄에 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 각 크레인의 무게 제한이 주어진다. 이 값은 1,000,000보다 작거나 같다. 셋째 줄에는 박스의 수 M이 주어진다. M은 10,000보

www.acmicpc.net

그리디 알고리즘 문제이다.

그리디가 약하다고 생각해서 풀어본 문제

결론적으로 두번 시간초과가 발생ㅋㅋㅋㅋ

풀이는 다음과 같다.

무거운 거를 옮기는 크레인들은 아래에있는 것들도 옮길 수 있다 라는 사실을 확인

그러면 내림차순으로 정렬 후에 각 크레인이 옮길 수 있는 것중에 제일 무거운거부터 이동하면 된다고 생각했다.
코드는 다음과 같다.

 

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
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int N, M;
vector<int> Crain; // 시작
vector<int> weight;
bool cmp(const int& a, const int& b) {
    return a > b;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> N;
    for (int i = 0; i < N; i++) {
        int num;
        cin >> num;
        Crain.push_back(num);
    }
    cin >> M;
    for (int i = 0; i < M; i++) {
        int num;
        cin >> num;
        weight.push_back(num);
    }
    sort(Crain.begin(), Crain.end(), cmp);
    sort(weight.begin(), weight.end(), cmp);
    int cnt = 0;
    if (weight[0] > Crain[0]) {
        cout << -1 << endl;
        return 0;
    }
    int size = M;
    while (!weight.empty()) {
        int index = 0;
        for (int i = 0; i < size; i++) {
            if (index == N) {
                break;
            }
            if (Crain[index] >= weight[i]) {
                index++;
                size--;
                weight.erase(weight.begin() + i);
                i = i - 1;
            }
        }
        cnt++;
    }
    cout << cnt << endl;
 
 
}
 cs

'BAEKJOON ONLINE JUDGE' 카테고리의 다른 글

[백준 14499] 주사위 굴리기 (C++)  (0) 2021.08.21
[백준 3190] 뱀 (C++)  (0) 2021.08.21
[백준 19237] 어른 상어 (C++)  (0) 2021.08.21
[백준 17090] 미로 탈출하기 (C++)  (0) 2021.08.20
[백준 14890] 경사로 (C++)  (0) 2021.08.20

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

 

19237번: 어른 상어

첫 줄에는 N, M, k가 주어진다. (2 ≤ N ≤ 20, 2 ≤ M ≤ N2, 1 ≤ k ≤ 1,000) 그 다음 줄부터 N개의 줄에 걸쳐 격자의 모습이 주어진다. 0은 빈칸이고, 0이 아닌 수 x는 x번 상어가 들어있는 칸을 의미

www.acmicpc.net

바보같이 3번 틀린 문제, M을 N으로 쓰는..바보같은 짓을 했다.

코드의 진행과정은 다음과 같다.

MAP과 Shark 구조체 선언

MAP에는 smell_count와 size 즉 상어의 크기,

Shark에는 x, y, dir, 우선순위 방향, 생사 유무가 저장되어있다.

input에서부터 고민하게 되는 문제이다.
N,M,K를 입력 받은 후 MAP의 정보를 입력 받는다. 이때 상어의 위치도 같이 저장.
그 다음 상어의 방향을 입력 받을때는 상어의 생사 유무도 입력받는다.
그 다음은 상어의 방향 우선순위이다, 방향은 Shark 구조체 안에 [5][5] 배열을 넣어줘서 사용한다.
solve 함수는 4가지 함수로 돌아간다.
첫번째 move 함수,
상어가 움직일 수 있는 위치를 확인한다. 그리고 shark_info 배열에 바뀐 위치와 방향을 저장
이때 map은 건드리지않는다.
두번째 kill_and_move함수

상어가 맵에서 움직이는 함수이다. 움직일때 1번부터 순서대로 이동하므로, 만약 이동하는 칸에 상어가 있으면,
그 상어는 숫자가 작은 함수 이므로, 늦게 움직이는 상어는 죽는다.
세번째는 smell_processing함수

상어의 냄새를 처리 하는 함수, 처음에는 bfs로 냄새의 위치를 탐색 할려 했지만, 맵이 20*20이므로, 그냥 모두 확인
냄새를 다 -- 해준다, 그리고 이동한 곳의 냄새는 K로 초기화한다,
네번째는 모두 false인지 check하는 함수이다.
여기서 M을 N으로 써서 4번틀림 ㅇㅇ

전체 코드는 다음과 같다.

 

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
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
#include <iostream>
#include <deque>
#include <utility>
#include <vector>
#include <queue>
using namespace std;
struct MAP {
    int smell_count;
    int size;
};
struct Shark {
    int x, y;
    int dir;
    int prior_dir[5][5];
    bool alive;
};
// 위 아래 왼쪽 오른쪽
int dx[5] = { 0,-1,1,0,0 };
int dy[5] = { 0,0,0,-1,1 };
// 변수들
int N, M, K;
Shark SHARK_INFO[401];
MAP MAP_INFO[21][21];
// 냄새가 있는 좌표 관리
bool check_range(int& next_x, int& next_y) {
    if (next_x >= 1 && next_y >= 1 && next_x <= N && next_y <= N)
        return true;
    else
        return false;
}
bool check_shark() {
    for (int i = 2; i <= M; i++) {
        if (SHARK_INFO[i].alive == true) {
            return false;
        }
    }
    return true;
}
void smell_Processing() {
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            if (MAP_INFO[i][j].smell_count != 0) {
                MAP_INFO[i][j].smell_count--;
                if (MAP_INFO[i][j].smell_count == 0) {
                    MAP_INFO[i][j].size = 0;
                }
            }
        }
    }
    for (int i = 1; i <= M; i++) {
        if (SHARK_INFO[i].alive == false)
            continue;
        int x = SHARK_INFO[i].x;
        int y = SHARK_INFO[i].y;
        MAP_INFO[x][y].size = i;
        MAP_INFO[x][y].smell_count = K;
    }
}
void kill_and_move() {
    for (int i = 1; i <= M; i++) {
        if (SHARK_INFO[i].alive == false) 
            continue;
        int x = SHARK_INFO[i].x;
        int y = SHARK_INFO[i].y;
        //cout << SHARK_INFO[i].x << SHARK_INFO[i].y << endl;
        if (MAP_INFO[x][y].size == 0 || MAP_INFO[x][y].size == i)
            MAP_INFO[x][y].size = i;
        else 
            SHARK_INFO[i].alive = false;
    }
}
void move() {
    for (int i = 1; i <= M; i++) {
        if (SHARK_INFO[i].alive == false)
            continue;
        // 처음에는 우선 순위로 빈칸 이동 확인하기
        int dir = SHARK_INFO[i].dir;
        bool flag = false;
        for (int j = 1; j <= 4; j++) {
            int next_x = SHARK_INFO[i].x + dx[SHARK_INFO[i].prior_dir[dir][j]];
            int next_y = SHARK_INFO[i].y + dy[SHARK_INFO[i].prior_dir[dir][j]];
            if (check_range(next_x, next_y) && MAP_INFO[next_x][next_y].size == 0) {
                SHARK_INFO[i].dir = SHARK_INFO[i].prior_dir[dir][j];
                SHARK_INFO[i].x = next_x;
                SHARK_INFO[i].y = next_y;
                flag = true;
                break;
            }
        }
        if (flag == true)
            continue;
        // 자기 냄새 칸으로 우선 순위 지켜서 이동
        for (int j = 1; j <= 4; j++) {
            int next_x = SHARK_INFO[i].x + dx[SHARK_INFO[i].prior_dir[dir][j]];
            int next_y = SHARK_INFO[i].y + dy[SHARK_INFO[i].prior_dir[dir][j]];
            if (check_range(next_x, next_y) && MAP_INFO[next_x][next_y].size == i) {
                SHARK_INFO[i].dir = SHARK_INFO[i].prior_dir[dir][j];
                SHARK_INFO[i].x = next_x;
                SHARK_INFO[i].y = next_y;
                break;
            }
        }
    }
}
void solve() {
    // 이동 할 칸 확인하기
    int day = 0;
    while (day < 1000){
        day++;
        move();
        kill_and_move();
        smell_Processing();
        if (check_shark() == true) {
            cout << day << endl;
            return;
        }
    }
    cout << -1 << endl;
}
void input() {
    cin >> N >> M >> K;
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            cin >> MAP_INFO[i][j].size;
            if (MAP_INFO[i][j].size != 0) {
                SHARK_INFO[MAP_INFO[i][j].size].x = i;
                SHARK_INFO[MAP_INFO[i][j].size].y = j;
                MAP_INFO[i][j].smell_count = K;
            }
        }
    }
    for (int i = 1; i <= M; i++) {
        cin >> SHARK_INFO[i].dir;
        SHARK_INFO[i].alive = true;
    }
    for (int i = 1; i <= M; i++) {
        for (int j = 1; j <= 4; j++) {
            for (int k = 1; k <= 4; k++) {
                cin >> SHARK_INFO[i].prior_dir[j][k];
            }
        }
    }
}
void init() {
    ios::sync_with_stdio(false);
    cin.tie(0);
}
int main() {
    init();
    input();
    solve();
}
 cs

'BAEKJOON ONLINE JUDGE' 카테고리의 다른 글

[백준 3190] 뱀 (C++)  (0) 2021.08.21
[백준 1092] 배 (C++)  (0) 2021.08.21
[백준 17090] 미로 탈출하기 (C++)  (0) 2021.08.20
[백준 14890] 경사로 (C++)  (0) 2021.08.20
[백준 19236] 청소년 상어 (C++)  (0) 2021.08.19

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

 

17090번: 미로 탈출하기

크기가 N×M인 미로가 있고, 미로는 크기가 1×1인 칸으로 나누어져 있다. 미로의 각 칸에는 문자가 하나 적혀있는데, 적혀있는 문자에 따라서 다른 칸으로 이동할 수 있다. 어떤 칸(r, c)에 적힌 문

www.acmicpc.net

시간을 최대한 쾌적하게 사용해야한다.

총 4번의 시도 끝에 성공..

처음 방법

그냥 일반적으로 탐색하다가 밖에 나오면 성공!으로 했지만, 실패

두번째는 q_history를 만들어 성공한 경우 탐색한 칸들은 MAP_CHECK배열에 true로 넣어 그 칸에 도착시 자동으로
탈출이 가능하다고 했다. 하지만 또 시간초가

세번재는 q_history를 통해서 탈출하지 못하는 경우도 MAP_CHECK_NOT배열에 true로 전달, 그 칸에 도착시 자동으로
탈출 못하는 하지만 실패
다음 방법은 방문 여부를 확인하는 check배열을 밖으로 빼어 매번 false로 초기화 하는 방식이 아닌, 성공하든 실패하든
check을 false로 만드는 방법 , 즉 이동경로를 확인하는 q_history가 있으므로, 그걸로 false로 초기화, 결과는 성공.
코드는 다음과 같다.

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
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
#include <iostream>
#include <queue>
using namespace std;
int N, M;
char MAP[501][501];
bool MAP_CHECK[501][501];
bool MAP_CHECK_NOT[501][501];
bool check[501][501] = { false };
// U R D L
int dx[4] = { -1,0,1,0 };
int dy[4] = { 0,1,0,-1 };
int count_res = 0;
void check_clean(int index, queue<pair<int,int>> &q_history) {
    if (index == 0) {
        while (!q_history.empty()) {
            MAP_CHECK_NOT[q_history.front().first][q_history.front().second] = true;
            check[q_history.front().first][q_history.front().second] = false;
            q_history.pop();
        }
    }
    else if (index == 1) {
        while (!q_history.empty()) {
            MAP_CHECK[q_history.front().first][q_history.front().second] = true;
            check[q_history.front().first][q_history.front().second] = false;
            q_history.pop();
        }
    }
}
int dir_check(char c) {
    if (c == 'U')
        return 0;
    else if (c == 'R')
        return 1;
    else if (c == 'D')
        return 2;
    else if (c == 'L')
        return 3;
}
void solve(int x,int y) {
    check[x][y] = true;
    queue<pair<int, int>> q;
    queue<pair<int, int>> q_history;
    q.push(make_pair(x, y));
    //cout << x << y << endl;
    while (!q.empty()) {
        int prev_x = q.front().first;
        int prev_y = q.front().second;
        int dir = dir_check(MAP[prev_x][prev_y]);
        q_history.push(make_pair(prev_x,prev_y));
        if (MAP_CHECK[prev_x][prev_y] == true) {
            check_clean(1, q_history);
            count_res++;
            return;
        }
        if (MAP_CHECK_NOT[prev_x][prev_y] == true) {
            check_clean(0, q_history);
            return;
        }
        q.pop();
        int next_x = prev_x + dx[dir];
        int next_y = prev_y + dy[dir];
        if (next_x >= 1 && next_y >= 1 && next_x <= N && next_y <= M) {
            if (check[next_x][next_y] == false) {
                check[next_x][next_y] = true;
                q.push(make_pair(next_x, next_y));
            }
            else {
                check_clean(0, q_history);
                return;
            }
        }
        else {
            check_clean(1, q_history);
            count_res++;
            return;
        }
    }
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> N >> M;
    for (int i = 1; i <= N; i++)
        for (int j = 1; j <= M; j++)
            cin >> MAP[i][j];
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= M; j++) {
            solve(i, j);
        }
    }
    cout << count_res << endl;
}
 cs

'BAEKJOON ONLINE JUDGE' 카테고리의 다른 글

[백준 1092] 배 (C++)  (0) 2021.08.21
[백준 19237] 어른 상어 (C++)  (0) 2021.08.21
[백준 14890] 경사로 (C++)  (0) 2021.08.20
[백준 19236] 청소년 상어 (C++)  (0) 2021.08.19
[백준 20057] 마법사 상어와 토네이도 (C++)  (0) 2021.08.18

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

 

14890번: 경사로

첫째 줄에 N (2 ≤ N ≤ 100)과 L (1 ≤ L ≤ N)이 주어진다. 둘째 줄부터 N개의 줄에 지도가 주어진다. 각 칸의 높이는 10보다 작거나 같은 자연수이다.

www.acmicpc.net

골드3 문제지만 생각만 잘 하면 30분이면 해결가능하다.

시간도 2초로 매우 넉넉하다..

코드는 매우 간단하다.

row와 col를 벡터로 선언하여 전달한다. 각 downhill이 가능한지 check하기 위해 복사하여 넘기는 방식으로 하였다.
Downhill_Discrimination 함수에서는 다음과 같은 과정으로 경사로가 가능한지 check한다.

bool check[100]을 선언한다.
L=2일때 앞뒤로 경사로가 겹치는 경우, 즉 내려갔다 올라가는 경우 평지가 4가 필요한데 , 4보다 적은 것을 check하기 위한것이다. 

이때 내려가는 부분먼저 check한다. 높이가 2이상 차이나면 return;

line[i] - line[i+1]이 1, 즉 내려가는 방향이면 둘 수 있는지 확인한다.
확인 방식은 L개만큼 연속된 평지가 있어야 하므로 첫번째 IF문은 조건이 i+count < N 이다. index안에서만 해결
그 다음은 평지인지와 check[i+count]가 false인지 check한다.
지금 생각하니 내리막에서는 딱히 check를 할 필요가 없을거 가다.

 

오르막은 똑같다, 이것은 N-1부터 1까지 check한다.
논리는 모두 같다. 

전체코드는 다음과 같다.

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
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
// 경사로
#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
struct check_hill {
    int index;
    int up_down; // -1 이면 올라가는 방향 , 1 이면 내려가는 방향, 0 
};
int N, L;
int MAP[100][100];
int count_res = 0;
void Downhill_Discrimination(vector<int>& line) {
    // 경우의 수
    // 우선 높이 차이가 2이면 return
    bool check[100] = { false };
    // 내려가는거 체크
    for (int i = 0; i < N - 1; i++) {
        if (abs(line[i] - line[i + 1]) >= 2)
            return;
        if (line[i] - line[i + 1] == 1) { // 내려 가는 방향이면
            int level = line[i + 1];
            for (int count = 1; count <= L; count++) {
                if (i + count < N) {
                    if (level == line[i + count] && check[i+count] == false) {
                        check[i+count] = true;
                    }
                    else {
                        return;
                    }
                }
                else {
                    return;
                }
            }
        }
    }
    // 올라가는거 체크
    for (int i = N - 1; i > 0; i--) {
        if (abs(line[i] - line[i - 1]) >= 2)
            return;
        if (line[i] - line[i - 1] == 1) {
            int level = line[i - 1];
            for (int count = 1; count <= L; count++) {
                if (i - count > -1) {
                    if (level == line[i - count] && check[i - count] == false) {
                        check[i - count] = true;
                    }
                    else {
                        return;
                    }
                }
                else {
                    return;
                }
            }
        }
    }
    count_res++;
}
void solve() {
    // 행열 처리
    for (int i = 0; i < N; i++) {
        vector<int> row;
        vector<int> col;
        for (int j = 0; j < N; j++) {
            row.push_back(MAP[i][j]);
            col.push_back(MAP[j][i]);
        }
        Downhill_Discrimination(row);
        Downhill_Discrimination(col);
    }
    cout << count_res << endl;
}
void input() {
    cin >> N >> L;
    for (int i = 0; i < N; i++)
        for (int j = 0; j < N; j++)
            cin >> MAP[i][j];
}
void init() {
    cin.tie(0)->sync_with_stdio(false);
}
int main() {
    init();
    input();
    solve();
}
 cs

'BAEKJOON ONLINE JUDGE' 카테고리의 다른 글

[백준 19237] 어른 상어 (C++)  (0) 2021.08.21
[백준 17090] 미로 탈출하기 (C++)  (0) 2021.08.20
[백준 19236] 청소년 상어 (C++)  (0) 2021.08.19
[백준 20057] 마법사 상어와 토네이도 (C++)  (0) 2021.08.18
[백준 17837] 새로운 게임 2 (C++)  (0) 2021.08.17

+ Recent posts

티스토리툴바