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/21611

 

21611번: 마법사 상어와 블리자드

마법사 상어는 파이어볼, 토네이도, 파이어스톰, 물복사버그, 비바라기 마법을 할 수 있다. 오늘 새로 배운 마법은 블리자드이고, 크기가 N×N인 격자에서 연습하려고 한다. N은 항상 홀수이고, (

www.acmicpc.net

지금까지 푼 문제중에 제일 오래 걸리고 제일 많이 틀린 문제이다.. 나에게 좌절감을 준 문제.

틀린 횟수...

내가 잘못 생각한 부분이 있었는데, 이 생각을 고치지 않아서 계속해서 틀린것이다.
나는 이 방식으로 진행했다.
1. N*N 맵을 일자로 핀다, 그 네모난 맵에는 들린 순서대로 1,2,3,,,, N*N -1 숫자를 부여한다.
2. 그리고 마법을 일으킨다. 이때 마법이 일어나면 아까 초기맵에 들린 순서대로 숫자를 부여 했으므로, 일자로 펼친 맵의 몇번쨰 index를 삭제하는지 알 수 있다.
3. 그 다음은 블럭을 터트린다. 이떄 일자 맵에 있는 것을 deque를 이용해 (횟수,숫자) 이 양식을 지켜 만든다.
터트린 블록은 제외한다.(터트린 블럭은 index를 알고 잇으므로, index가 같은 거는 그냥 continue)
4. 그리고 점수를 얻는 과정이다. 
우선 주의해야할게 많다. 나는 기존에 터트리자마자 배열을 앞으로 이동, 또 숫자가 겹치면 터트리게 하였다.

하지만 문제를 보면, 모두 터트리고 난 뒤에 다시 숫자를 움직이는 것을 알 수 있었다..
5. 그 다음에는 맵을 다시 일자로 만들어준다, 이 경우는 위에 횟수 숫자로 해놨기 때문에 쉽다.

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
// 마법사 상어와 블리자드 21611번
#include <iostream>
#include <vector>
#include <utility>
#include <deque>
#define MAX 50
using namespace std;
int N, M;
// ↑, ↓, ←, →
int pop_dx[5] = { 0,-1,1,0,0 };
int pop_dy[5] = { 0,0,0,-1,1 };
// ←, ↓, →, ↑ 일짜로 피는 과정
int dx[4] = { 0,1,0,-1 };
int dy[4] = { -1,0,1,0 };
int MAP[MAX][MAX];
vector<pair<int, int>> operation;
// 처음부터 맵을 피고, 저렇게 할 때만 맵을 새로 만든다 그리고 다시 벡터로 맵 만들고
deque<pair<int, int>> map_1;
deque<int> map_2;
deque<int> magic_pop;
int total_count = 0;
void turn(int& x, int& y, int& dir, int& index, int& count) {
    for (int i = 0; i < index; i++) {
        x += dx[dir];
        y += dy[dir];
        if (MAP[x][y] == 0) {
            MAP[x][y] = count++;
        }
        else {
            map_2.push_back(MAP[x][y]);
            MAP[x][y] = count++;
        }
    }
    dir += 1;
    if (dir == 4)
        dir = 0;
}
void make_in_a_row() {
    // map2 만들고, MAP을 순서에 따라 index
    int x = N / 2 + 1;
    int y = N / 2 + 1;
    int dir = 0;
    int index = 1;
    int count = 1;
    map_2.push_back(0);
    while (x != 1 || y != 1) {
        if (index == N - 1) {
            turn(x, y, dir, index, count);
            turn(x, y, dir, index, count);
            turn(x, y, dir, index, count);
        }
        else {
            turn(x, y, dir, index, count);
            turn(x, y, dir, index, count);
            index++;
        }
    }
}
void pop_marble() {
    for (int i = 0; i < map_2.size(); i++) {
        if (!magic_pop.empty() && i == magic_pop.front()) {
            magic_pop.pop_front();
            continue;
        }
        if (map_2[i] == 0)
            map_1.push_back(make_pair(0, 0));
        else if (map_1.back().second == map_2[i])
            map_1.back().first++;
        else 
            map_1.push_back(make_pair(1, map_2[i]));
    }
    map_2.clear();
    magic_pop.clear();
    bool flag = false;
    while (flag == false) {
        deque<pair<int, int>> temp;
        flag = true;
        temp.push_back(map_1.front());
        map_1.pop_front();
        while (!map_1.empty()) {
            if (map_1.front().first >= 4) {
                total_count += map_1.front().first * map_1.front().second;
                map_1.pop_front();
                flag = false;
                continue;
            }
            if (temp.back().second == map_1.front().second) {
                temp.back().first += map_1.front().first;
                map_1.pop_front();
                continue;
            }
            temp.push_back(map_1.front());
            map_1.pop_front();
        }
        map_1 = temp;
    }
    int count = 0;
    for (auto i : map_1) {
        if (i.first == 0) {
            map_2.push_front(0);
            continue;
        }
        if (count == N * N - 1) {
            break;
        }
        map_2.push_back(i.first);
        map_2.push_back(i.second);
        count += 2;
    }
    map_1.clear();
}
void magic(const int& dir, const int& size) {
    int x = N / 2 + 1;
    int y = N / 2 + 1;
    for (int i = 0; i < size; i++) {
        x += pop_dx[dir];
        y += pop_dy[dir];
        magic_pop.push_back(MAP[x][y]);
    }
}
void solve() {
    make_in_a_row();
    for (auto i : operation) {
        magic(i.first, i.second);
        pop_marble();
    }
    cout << total_count << endl;
}
void input() {
    cin >> N >> M;
    for (int i = 1; i <= N; i++)
        for (int j = 1; j <= N; j++)
            cin >> MAP[i][j];
    for (int i = 1; i <= M; i++) {
        int dir, size;
        cin >> dir >> size;
        operation.push_back(make_pair(dir, size));
    }
}
void init() {
    ios::sync_with_stdio(false);
    cin.tie(0);
}
int main() {
    init();
    input();
    solve();
}
 cs

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

[백준 13164] 행복 유치원 (C++)  (0) 2021.08.27
[백준 11000] 강의실 배정 (C++)  (0) 2021.08.27
[백준 20061] 모노미노도미노 2 (C++)  (0) 2021.08.23
[백준 21609] 상어 중학교 (C++)  (0) 2021.08.22
[백준 14499] 주사위 굴리기 (C++)  (0) 2021.08.21

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

 

20061번: 모노미노도미노 2

모노미노도미노는 아래와 같이 생긴 보드에서 진행되는 게임이다. 보드는 빨간색 보드, 파란색 보드, 초록색 보드가 그림과 같이 붙어있는 형태이다. 게임에서 사용하는 좌표 (x, y)에서 x는 행,

www.acmicpc.net

생각보다 까다로운 문제.

크게 4가지  함수로 구현했다.

하나는 block_add , 그 다음은 check_point, 그 다음은 연한색 영역인 check_soft, 그 다음은 블록 행또는 열을 지워주는
down_block_point_or_disappear 함수.

1
2
3
4
5
6
7
#include <iostream>
#include <deque>
using namespace std;
int map[10][10];
int N, T, X, Y;
int block[4][2] = { {0,0},{0,0},{0,1},{1,0} };
int total_result = 0;
 cs

다음과 같이 변수들을 전역으로 사용했다.

map는 그냥 10*10이다. 초록색 파란색을 따로 선언할까 하는 생각을 했지만, 이게 더 편한거같다. 간편하게 행과 열만 바꿔서 생각하면된다.
block은 다음과 같이 한 이유는 이따가 설명, 뭐 대충보면 두개인 경우 한개 인 경우가 있으므로 저렇게 한 것이다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void solve() {
    cin >> N;
    for (int i = 0; i < N; i++) {
        cin >> T >> X >> Y;
        block_add();
        check_point();
        check_soft();
    }
    cout << total_result << endl;
    int count = 0;
    for (int i = 0; i < 10; i++) {
        for (int j = 0; j < 10; j++) {
            if (map[i][j] == 1)
                count++;
        }
    }
    cout << count << endl;
}
 cs

solve함수 이다. 입력과 동시에 block_add, check_point, check_soft가 작동한다.
block_add함수는 다음과 같다.

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
void block_add() {
    int x1 = X;
    int x2 = X + block[T][0];
    int y1 = Y;
    int y2 = Y + block[T][1];
    while (1) {
        if (x1 == 10 || x2 == 10) {
            x1--, x2--;
            break;
        }
        if (map[x1][y1] == 1 || map[x2][y2] == 1) {
            x1--, x2--;
            break;
        }
        else {
            x1++, x2++;
        }
    }
    map[x1][y1] = 1; map[x2][y2] = 1;
    x1 = X;
    x2 = X + block[T][0];
    y1 = Y;
    y2 = Y + block[T][1];
    while (1) {
        if (y1 == 10 || y2 == 10) {
            y1--, y2--;
            break;
        }
        if (map[x1][y1] == 1 || map[x2][y2] == 1) {
            y1--, y2--;
            break;
        }
        else {
            y1++, y2++;
        }
    }
    map[x1][y1] = 1; map[x2][y2] = 1;
}
 cs

block_add 함수 이다. 이름과 같이 block을 추가하는 함수.
블럭은 많아도 좌표가 두개이다. 그러므로 다음과 같이 구현했다.
입력 받은(x,y), (x+dx[type][0], y+dy[type][1]) 이다. 
블럭이 내려가는 과정은 중력과 같다. 그냥 두개의 x1,x2좌표, 또는 y1,y2좌표의 map칸이 1이 아니고, 9이하이면 된다.

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
void check_point() {
    for (int i = 6; i <= 9; i++) {
        int count = 0;
        for (int j = 0; j < 4; j++) {
            if (map[i][j] == 1)
                count++;
        }
        if (count == 4) {
            for (int j = 0; j < 4; j++) {
                map[i][j] = 0;
            }
            total_result++;
            down_block_point_or_disappear(i, 1);
        }
    }
    for (int j = 6; j <= 9; j++) {
        int count= 0;
        for (int i = 0; i < 4; i++) {
            if (map[i][j] == 1)
                count++;
        }
        if (count == 4) {
            for (int i = 0; i < 4; i++) {
                map[i][j] = 0;
            }
            total_result++;
            down_block_point_or_disappear(j, 0);
        }
    }
}
 cs

포인트를 얻는 과정, 여기선 그냥 연한칸을 제외하고 행과 열에서 1이 4개인 것을 count해서 이 행을 0으로 만든  뒤에 점수를 1점 더해주면된다.
그리고 블록이 위에서 내려오는 과정은 down_block_point_or_disappear로 구현했다.
0이면 푸른색, 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
void down_block_point_or_disappear(int index, int line) { // line 0 이면 블루, 1 이면 그린
    deque<int> dq;
    if (line == 1) {
        for (int i = 4; i <= index - 1; i++) {
            for (int j = 0; j < 4; j++) {
                dq.push_back(map[i][j]);
                map[i][j] = 0;
            }
        }
        for (int i = 5; i <= index; i++) {
            for (int j = 0; j < 4; j++) {
                map[i][j] = dq.front();
                dq.pop_front();
            }
        }
    }
    else {
        for (int j = 4; j <= index - 1; j++) {
            for (int i = 0; i < 4; i++) {
                dq.push_back(map[i][j]);
                map[i][j] = 0;
            }
        }
        for (int j = 5; j <= index; j++) {
            for (int i = 0; i < 4; i++) {
                map[i][j] = dq.front();
                dq.pop_front();
            }
        }
    }
}
 cs

이 함수는 대충 이런느낌이다. 포인트를 얻거나, 연한색에서 사라지면 위에줄을 한줄 내리는 방식,
dq에 순서를 맞춰서 넣은 다음에, 아래쪽 줄로 한줄 내려서 넣는다.

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
void check_soft() {
    int count = 0;
    for (int i = 4; i < 6; i++) {
        for (int j = 0; j < 4; j++) {
            if (map[i][j] == 1) {
                count++;
                break;
            }
        }
    }
    for (int i = 0; i < count; i++) {
        down_block_point_or_disappear(9, 1);
    }
    count = 0;
    for (int j = 4; j < 6; j++) {
        for (int i = 0; i < 4; i++) {
            if (map[i][j] == 1) {
                count++;
                break;
            }
        }
    }
    for (int i = 0; i < count; i++) 
        down_block_point_or_disappear(9, 0);
}
 cs

check soft함수 연한색에 블럭이 있으면, 맨 아래 행이나 열을 삭제한다.
맨 아래 행이나 열 이므로 9가 들어간다.
전체 코드는 다음과 같다.

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
167
168
169
170
171
172
173
174
175
#include <iostream>
#include <deque>
using namespace std;
int map[10][10];
int N, T, X, Y;
int block[4][2] = { {0,0},{0,0},{0,1},{1,0} };
int total_result = 0;
void print() {
    cout << "green" << endl;
    for (int i = 4; i <= 9; i++) {
        for (int j = 0; j < 4; j++) {
            cout << map[i][j] << " ";
        }
        cout << endl;
    }
    cout << endl;
    cout << "blue" << endl;
    for (int i = 0; i < 4; i++) {
        for (int j = 4; j <= 9; j++) {
            cout << map[i][j] << " ";
        }
        cout << endl;
    }
    cout << endl;
}
void down_block_point_or_disappear(int index, int line) { // line 0 이면 블루, 1 이면 그린
    deque<int> dq;
    if (line == 1) {
        for (int i = 4; i <= index - 1; i++) {
            for (int j = 0; j < 4; j++) {
                dq.push_back(map[i][j]);
                map[i][j] = 0;
            }
        }
        for (int i = 5; i <= index; i++) {
            for (int j = 0; j < 4; j++) {
                map[i][j] = dq.front();
                dq.pop_front();
            }
        }
    }
    else {
        for (int j = 4; j <= index - 1; j++) {
            for (int i = 0; i < 4; i++) {
                dq.push_back(map[i][j]);
                map[i][j] = 0;
            }
        }
        for (int j = 5; j <= index; j++) {
            for (int i = 0; i < 4; i++) {
                map[i][j] = dq.front();
                dq.pop_front();
            }
        }
    }
}
void check_soft() {
    int count = 0;
    for (int i = 4; i < 6; i++) {
        for (int j = 0; j < 4; j++) {
            if (map[i][j] == 1) {
                count++;
                break;
            }
        }
    }
    for (int i = 0; i < count; i++) {
        down_block_point_or_disappear(9, 1);
    }
    count = 0;
    for (int j = 4; j < 6; j++) {
        for (int i = 0; i < 4; i++) {
            if (map[i][j] == 1) {
                count++;
                break;
            }
        }
    }
    for (int i = 0; i < count; i++) 
        down_block_point_or_disappear(9, 0);
}
void check_point() {
    for (int i = 6; i <= 9; i++) {
        int count = 0;
        for (int j = 0; j < 4; j++) {
            if (map[i][j] == 1)
                count++;
        }
        if (count == 4) {
            for (int j = 0; j < 4; j++) {
                map[i][j] = 0;
            }
            total_result++;
            down_block_point_or_disappear(i, 1);
        }
    }
    for (int j = 6; j <= 9; j++) {
        int count= 0;
        for (int i = 0; i < 4; i++) {
            if (map[i][j] == 1)
                count++;
        }
        if (count == 4) {
            for (int i = 0; i < 4; i++) {
                map[i][j] = 0;
            }
            total_result++;
            down_block_point_or_disappear(j, 0);
        }
    }
}
void block_add() {
    int x1 = X;
    int x2 = X + block[T][0];
    int y1 = Y;
    int y2 = Y + block[T][1];
    while (1) {
        if (x1 == 10 || x2 == 10) {
            x1--, x2--;
            break;
        }
        if (map[x1][y1] == 1 || map[x2][y2] == 1) {
            x1--, x2--;
            break;
        }
        else {
            x1++, x2++;
        }
    }
    map[x1][y1] = 1; map[x2][y2] = 1;
    x1 = X;
    x2 = X + block[T][0];
    y1 = Y;
    y2 = Y + block[T][1];
    while (1) {
        if (y1 == 10 || y2 == 10) {
            y1--, y2--;
            break;
        }
        if (map[x1][y1] == 1 || map[x2][y2] == 1) {
            y1--, y2--;
            break;
        }
        else {
            y1++, y2++;
        }
    }
    map[x1][y1] = 1; map[x2][y2] = 1;
}
void solve() {
    cin >> N;
    for (int i = 0; i < N; i++) {
        cin >> T >> X >> Y;
        block_add();
        check_point();
        check_soft();
    }
    cout << total_result << endl;
    int count = 0;
    for (int i = 0; i < 10; i++) {
        for (int j = 0; j < 10; j++) {
            if (map[i][j] == 1)
                count++;
        }
    }
    cout << count << endl;
}
void init() {
    ios::sync_with_stdio(false);
    cin.tie(0);
}
int main() {
    init();
    solve();
}
 cs

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

[백준 11000] 강의실 배정 (C++)  (0) 2021.08.27
[백준 21611] 마법사 상어와 블리자드 (C++)  (0) 2021.08.26
[백준 21609] 상어 중학교 (C++)  (0) 2021.08.22
[백준 14499] 주사위 굴리기 (C++)  (0) 2021.08.21
[백준 3190] 뱀 (C++)  (0) 2021.08.21

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/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

+ Recent posts

티스토리툴바