문제

아기 상어가 성장해 청소년 상어가 되었다.

4×4크기의 공간이 있고, 크기가 1×1인 정사각형 칸으로 나누어져 있다. 공간의 각 칸은 (x, y)와 같이 표현하며, x는 행의 번호, y는 열의 번호이다. 한 칸에는 물고기가 한 마리 존재한다. 각 물고기는 번호와 방향을 가지고 있다. 번호는 1보다 크거나 같고, 16보다 작거나 같은 자연수이며, 두 물고기가 같은 번호를 갖는 경우는 없다. 방향은 8가지 방향(상하좌우, 대각선) 중 하나이다.

오늘은 청소년 상어가 이 공간에 들어가 물고기를 먹으려고 한다. 청소년 상어는 (0, 0)에 있는 물고기를 먹고, (0, 0)에 들어가게 된다. 상어의 방향은 (0, 0)에 있던 물고기의 방향과 같다. 이후 물고기가 이동한다.

물고기는 번호가 작은 물고기부터 순서대로 이동한다. 물고기는 한 칸을 이동할 수 있고, 이동할 수 있는 칸은 빈 칸과 다른 물고기가 있는 칸, 이동할 수 없는 칸은 상어가 있거나, 공간의 경계를 넘는 칸이다. 각 물고기는 방향이 이동할 수 있는 칸을 향할 때까지 방향을 45도 반시계 회전시킨다. 만약, 이동할 수 있는 칸이 없으면 이동을 하지 않는다. 그 외의 경우에는 그 칸으로 이동을 한다. 물고기가 다른 물고기가 있는 칸으로 이동할 때는 서로의 위치를 바꾸는 방식으로 이동한다.

물고기의 이동이 모두 끝나면 상어가 이동한다. 상어는 방향에 있는 칸으로 이동할 수 있는데, 한 번에 여러 개의 칸을 이동할 수 있다. 상어가 물고기가 있는 칸으로 이동했다면, 그 칸에 있는 물고기를 먹고, 그 물고기의 방향을 가지게 된다. 이동하는 중에 지나가는 칸에 있는 물고기는 먹지 않는다. 물고기가 없는 칸으로는 이동할 수 없다. 상어가 이동할 수 있는 칸이 없으면 공간에서 벗어나 집으로 간다. 상어가 이동한 후에는 다시 물고기가 이동하며, 이후 이 과정이 계속해서 반복된다.

<그림 1>

<그림 1>은 청소년 상어가 공간에 들어가기 전 초기 상태이다. 상어가 공간에 들어가면 (0, 0)에 있는 7번 물고기를 먹고, 상어의 방향은 ↘이 된다. <그림 2>는 상어가 들어간 직후의 상태를 나타낸다.

<그림 2>

이제 물고기가 이동해야 한다. 1번 물고기의 방향은 ↗이다. ↗ 방향에는 칸이 있고, 15번 물고기가 들어있다. 물고기가 있는 칸으로 이동할 때는 그 칸에 있는 물고기와 위치를 서로 바꿔야 한다. 따라서, 1번 물고기가 이동을 마치면 <그림 3>과 같아진다.

<그림 3>

2번 물고기의 방향은 ←인데, 그 방향에는 상어가 있으니 이동할 수 없다. 방향을 45도 반시계 회전을 하면 ↙가 되고, 이 칸에는 3번 물고기가 있다. 물고기가 있는 칸이니 서로 위치를 바꾸고, <그림 4>와 같아지게 된다.

<그림 4>

3번 물고기의 방향은 ↑이고, 존재하지 않는 칸이다. 45도 반시계 회전을 한 방향 ↖도 존재하지 않으니, 다시 회전을 한다. ← 방향에는 상어가 있으니 또 회전을 해야 한다. ↙ 방향에는 2번 물고기가 있으니 서로의 위치를 교환하면 된다. 이런 식으로 모든 물고기가 이동하면 <그림 5>와 같아진다.

<그림 5>

물고기가 모두 이동했으니 이제 상어가 이동할 순서이다. 상어의 방향은 ↘이고, 이동할 수 있는 칸은 12번 물고기가 있는 칸, 15번 물고기가 있는 칸, 8번 물고기가 있는 칸 중에 하나이다. 만약, 8번 물고기가 있는 칸으로 이동하면, <그림 6>과 같아지게 된다.

<그림 6>

상어가 먹을 수 있는 물고기 번호의 합의 최댓값을 구해보자.

입력

첫째 줄부터 4개의 줄에 각 칸의 들어있는 물고기의 정보가 1번 행부터 순서대로 주어진다. 물고기의 정보는 두 정수 ai, bi로 이루어져 있고, ai는 물고기의 번호, bi는 방향을 의미한다. 방향 bi는 8보다 작거나 같은 자연수를 의미하고, 1부터 순서대로 ↑, ↖, ←, ↙, ↓, ↘, →, ↗ 를 의미한다.

출력

상어가 먹을 수 있는 물고기 번호의 합의 최댓값을 출력한다.

예제 입력 1 

7 6 2 3 15 6 9 8
3 1 1 8 14 7 10 1
6 1 13 6 4 3 11 4
16 1 8 7 5 2 12 2

 

예제 출력 1 

33

예제 입력 2 

16 7 1 4 4 3 12 8
14 7 7 6 3 4 10 2
5 2 15 2 8 3 6 4
11 8 2 4 13 5 9 4

예제 출력 2 

43

예제 입력 3 

12 6 14 5 4 5 6 7
15 1 11 7 3 7 7 5
10 3 8 3 16 6 1 1
5 8 2 7 13 6 9 2

예제 출력 3 

76

예제 입력 4 

2 6 10 8 6 7 9 4
1 7 16 6 4 2 5 8
3 7 8 6 7 6 14 8
12 7 15 4 11 3 13 3

예제 출력 4 

39

 

풀이

문제를 읽자마자 재귀의 느낌이 들었다.
처음에 Fish_list와 Fish_map을 이용하여 초기상태를 저장하였다.
그 다음 solve함수에 전달, 맨 처음 한 일은 Fish_list에 따라 Fish_map을 초기화. 이렇게 한 이유는.. 재귀 할 때마다 
이유를 모르겟는 오류가 발생 ㅠ
그다음 Shark_state에 들어있는 값을 이용해 생선을 먹방...이때 상어가 이동하는데 거기가 0이면 return해버린다
먹은거를 정리 하고 총 16마리니깐 for문을 16번한다. 이때 size가 0, 이미먹힌거는 continue한다.
움직일 수 있는지 체크, 총 8번 for문을 돌린다. 이떄 0이냐, 0이아니냐에 따라 조건을 나눈다.. 
다시보니 조건을 나눌필요가 딱히 없을거같다.
dir은 +1씩하며 체크한다. 모두 이동이 끝나면! 상어 이동
상어가 이동하기 위해 next_x, next_y를 선언 및 상어위치 전달.
방향으로 이동하는데 이때 맵 범위 안이면 이동한다. 물고기 있는지는 위쪽에서 체크..
그다음은 뭐 재귀문을 계속돌린다..

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
// 청소년 상어
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
struct Fish
{
    int x, y;
    int size;
    int dir;
};
bool cmp(const Fish& a, const Fish& b) {
    return a.size < b.size;
}
int MAX_RES = 0;
// ↑, ↖, ←, ↙, ↓, ↘, →, ↗
int dx[9] = { 0, -1,-1,0,1,1,1,0,-1 };
int dy[9] = { 0, 0,-1,-1,-1,0,1,1,1 };
void solve(int Fish_Map[5][5], vector<Fish> Fish_list, Fish Shark_state, int total_size) {
    for (int i = 1; i <= 4; i++)
        for (int j = 1; j <= 4; j++)
            Fish_Map[i][j] = 0;
    for (int i = 1; i <= 16;i++) {
        if (Fish_list[i].size == 0)continue;
        Fish_Map[Fish_list[i].x][Fish_list[i].y] = Fish_list[i].size;
    }
    if (Fish_Map[Shark_state.x][Shark_state.y] == 0)
        return;
    // Shark_state에 size 할당 및 방향 choose
    Shark_state.size = Fish_Map[Shark_state.x][Shark_state.y];
    Shark_state.dir = Fish_list[Shark_state.size].dir;
    // 먹은거 정리
    Fish_Map[Shark_state.x][Shark_state.y] = 0;
    Fish_list[Shark_state.size].size = 0;
    total_size += Shark_state.size;
    MAX_RES = max(total_size, MAX_RES);
    // 물고기 이동
    for (int i = 1; i <= 16; i++) {
        if (Fish_list[i].size == 0) // 이미 상어가 먹어버린 물고기
            continue;
        for (int j = 1; j <= 8; j++) {
            int next_x = Fish_list[i].x + dx[Fish_list[i].dir];
            int next_y = Fish_list[i].y + dy[Fish_list[i].dir];
            // 범위 안 인지 체크
            if (next_x >= 1 && next_y >= 1 && next_x <= 4 && next_y <= 4) {
                // 다음 칸이 상어가 있는지 체크
                if (Shark_state.x != next_x || Shark_state.y != next_y) {
                    // 다음 칸이 빈칸 일 경우
                    if (Fish_Map[next_x][next_y] == 0) {
                        Fish_Map[Fish_list[i].x][Fish_list[i].y] = 0;
                        Fish_list[i].x = next_x;
                        Fish_list[i].y = next_y;
                        Fish_Map[next_x][next_y] = Fish_list[i].size;
                        break;
                    }
                    // 다음 칸이 빈칸이 아닌 경우
                    else {
                        int next_site_fish_size = Fish_Map[next_x][next_y];
                        Fish_list[next_site_fish_size].x = Fish_list[i].x;
                        Fish_list[next_site_fish_size].y = Fish_list[i].y;
                        Fish_list[i].x = next_x;
                        Fish_list[i].y = next_y;
                        Fish_Map[Fish_list[next_site_fish_size].x][Fish_list[next_site_fish_size].y] = next_site_fish_size;
                        Fish_Map[Fish_list[i].x][Fish_list[i].y] = Fish_list[i].size;
                        break;
                    }
                }
            }
            Fish_list[i].dir += 1;
            if (Fish_list[i].dir == 9) 
                Fish_list[i].dir = 1;
        }
    }
    int next_x = Shark_state.x;
    int next_y = Shark_state.y;
    while (1) {
        next_x = next_x + dx[Shark_state.dir];
        next_y = next_y + dy[Shark_state.dir];
        if (next_x >= 1 && next_y >= 1 && next_x <= 4 && next_y <= 4) {
            Fish temp;
            temp.x = next_x; temp.y = next_y; temp.size = 0; temp.dir = -1;
            solve(Fish_Map, Fish_list, temp, total_size);
        }
        else
            break;
    }
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    vector<Fish> Fish_list;
    Fish_list.push_back({ 0, 0, 0, 0 });
    int Fish_Map[5][5];
    for (int i = 1; i <= 4; i++) {
        for (int j = 1; j <= 4; j++) {
            int size, dir;
            cin >> size >> dir;
            Fish_list.push_back({ i,j,size,dir });
            Fish_Map[i][j] = size;
        }
    }
    sort(Fish_list.begin(), Fish_list.end(),cmp);
    solve(Fish_Map, Fish_list, { 1,1,0,-1 }, 0);
    cout << MAX_RES << endl;
}
 cs

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

[백준 17090] 미로 탈출하기 (C++)  (0) 2021.08.20
[백준 14890] 경사로 (C++)  (0) 2021.08.20
[백준 20057] 마법사 상어와 토네이도 (C++)  (0) 2021.08.18
[백준 17837] 새로운 게임 2 (C++)  (0) 2021.08.17
[백준 2206] 벽 부수고 이동하기 (C++)  (0) 2021.08.16

 

문제

마법사 상어가 토네이도를 배웠고, 오늘은 토네이도를 크기가 N×N인 격자로 나누어진 모래밭에서 연습하려고 한다. 위치 (r, c)는 격자의 r행 c열을 의미하고, A[r][c]는 (r, c)에 있는 모래의 양을 의미한다.

토네이도를 시전하면 격자의 가운데 칸부터 토네이도의 이동이 시작된다. 토네이도는 한 번에 한 칸 이동한다. 다음은 N = 7인 경우 토네이도의 이동이다.

토네이도가 한 칸 이동할 때마다 모래는 다음과 같이 일정한 비율로 흩날리게 된다.

토네이도가 x에서 y로 이동하면, y의 모든 모래가 비율과 α가 적혀있는 칸으로 이동한다. 비율이 적혀있는 칸으로 이동하는 모래의 양은 y에 있는 모래의 해당 비율만큼이고, 계산에서 소수점 아래는 버린다. α로 이동하는 모래의 양은 비율이 적혀있는 칸으로 이동하지 않은 남은 모래의 양과 같다. 모래가 이미 있는 칸으로 모래가 이동하면, 모래의 양은 더해진다. 위의 그림은 토네이도가 왼쪽으로 이동할 때이고, 다른 방향으로 이동하는 경우는 위의 그림을 해당 방향으로 회전하면 된다.

토네이도는 (1, 1)까지 이동한 뒤 소멸한다. 모래가 격자의 밖으로 이동할 수도 있다. 토네이도가 소멸되었을 때, 격자의 밖으로 나간 모래의 양을 구해보자.

입력

첫째 줄에 격자의 크기 N이 주어진다. 둘째 줄부터 N개의 줄에는 격자의 각 칸에 있는 모래가 주어진다. r번째 줄에서 c번째 주어지는 정수는 A[r][c] 이다.

출력

격자의 밖으로 나간 모래의 양을 출력한다.

제한

  • 3 ≤ N ≤ 499
  • N은 홀수
  • 0 ≤ A[r][c] ≤ 1,000
  • 가운데 칸에 있는 모래의 양은 0

예제 입력 1 

5
0 0 0 0 0
0 0 0 0 0
0 10 0 0 0
0 0 0 0 0
0 0 0 0 0

예제 출력 1 

10

예제 입력 2 

5
0 0 0 0 0
0 0 0 0 0
0 100 0 0 0
0 0 0 0 0
0 0 0 0 0

예제 출력 2 

85

예제 입력 3 

7
1 2 3 4 5 6 7
1 2 3 4 5 6 7
1 2 3 4 5 6 7
1 2 3 0 5 6 7
1 2 3 4 5 6 7
1 2 3 4 5 6 7
1 2 3 4 5 6 7

예제 출력 3 

139

예제 입력 4 

5
100 200 300 400 200
300 243 432 334 555
999 111 0 999 333
888 777 222 333 900
100 200 300 400 500

예제 출력 4 

7501

예제 입력 5 

5
0 0 100 0 0
0 0 100 0 0
0 0 0 0 0
0 0 100 0 0
0 0 100 0 0

예제 출력 5 

283

예제 입력 6 

9
193 483 223 482 858 274 847 283 748
484 273 585 868 271 444 584 293 858
828 384 382 818 347 858 293 999 727
818 384 727 373 636 141 234 589 991
913 564 555 827 0 999 123 123 123
321 321 321 983 982 981 983 980 990
908 105 270 173 147 148 850 992 113
943 923 982 981 223 131 222 913 562
752 572 719 590 551 179 141 137 731

22961

 

풀이

이동하는 경로만 간단하게 계산하면 쉬운 문제이다.

대충 이동경로를 생각해보자.

처음에는

N = 5 인 맵을 생각해보자 

← 1번,  ↓ 1번

그 다음에는

→ 2번,  ↑ 2번

그 다음에는

← 3번,  ↓ 3번

그 다음에는

→ 4번,  ↑ 4번 ← 4번 끝

이정도 쓰면 눈치 챌듯? 할거같네요. 방향은 반시계로 돌아가며, 1, 2, 3 이 두번 반복, 마지막 N-1번 이동시에는 연속3번 이동

이 규칙을 이해하면된다.

그리고 먼지 뿌리는건 현재 방향에서 -1, +1 방향으로 먼지를 뿌리고 남은 것을 알파에 뿌린다.

이떄 알파에 들어갈 먼지를 계산할때 유의 해야한다.. 

알파에 들어갈 먼지양을 계산시 int(이동하는 먼지양 * 0.01) 필수다. int *******

함수 리스트

void init();  // ios::~~`
void input(); // inpurt
void Move_Tornado(); // 토네이도를 계산하기 시작하는 함수
void move(); // 이동하는 것을 계산
void dust(); // 먼지가 퍼지는 것을 계산
bool check_map_range(int& next_x, int& next_y); // 맵 범위가 맞는지 계산

코드는 다음과 같다. 

 

 

 

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
#include <iostream>
#include <iomanip>
#define MAX 1000+1
using namespace std;
int N;
int A[MAX][MAX];
// 0    1      2      3
// 왼쪽 아래쪽 오른쪽 위쪽
int dx[4] = { 0,1,0,-1 };
int dy[4] = { -1,0,1,0 };
int Tornado_x; int Tornado_y;
int prev_x; int prev_y;
int dir = 0; int index = 1; int total = 0;
void init();
void input();
void Move_Tornado();
void move();
void dust();
bool check_map_range(int& next_x, int& next_y);
int main() {
    init();
    input();
    Move_Tornado();
}
void init() {
    ios::sync_with_stdio(false);
    cin.tie(0);
}
void input() {
    cin >> N;
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            cin >> A[i][j];
            total += A[i][j];
        }
    }
}
void Move_Tornado() {
    Tornado_x = N / 2 + 1;
    Tornado_y = N / 2 + 1;
    dir = 0;
    index = 1;
    A[Tornado_x][Tornado_y] = 0;
    while (Tornado_x != 1 || Tornado_y != 1) {
        if (index == N - 1) {
            move();
            move();
            move();
        }
        else {
            move();
            move();
            index++;
        }
    }
    int total_temp = 0;
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            total_temp += A[i][j];
        }
    }
    cout << total - total_temp;
}
void move() {
    for (int i = 0; i < index; i++) {
        prev_x = Tornado_x;
        prev_y = Tornado_y;
        Tornado_x += dx[dir];
        Tornado_y += dy[dir];
        dust();
    }
    dir += 1;
    if (dir == 4)
        dir = 0;
}
void dust() {
    // 0    1      2      3
    // 왼쪽 아래쪽 오른쪽 위쪽
    // x -> y -> a 순으로 먼지 날릴 양 계산
    // dir 방향에서 +1, -1 방향으로 퍼진다
    int dir_dust[2] = { dir + 1,dir - 1 };
    int dust_total = A[Tornado_x][Tornado_y];
    int alpah_dust = dust_total;
    A[Tornado_x][Tornado_y] = 0;
    int alpha_x = Tornado_x + dx[dir];
    int alpha_y = Tornado_y + dy[dir];
    if (dir_dust[0] == 4)
        dir_dust[0] = 0;
    if (dir_dust[1] == -1)
        dir_dust[1] = 3;
    for (int i = 0; i < 2; i++) {
        int next_x = prev_x + dx[dir_dust[i]];
        int next_y = prev_y + dy[dir_dust[i]];
        if (check_map_range(next_x, next_y) == true) {
            A[next_x][next_y] += dust_total * 0.01;
        }
        alpah_dust -= int(dust_total * 0.01);
    }
    for (int i = 0; i < 2; i++) {
        int next_x = Tornado_x;
        int next_y = Tornado_y;
        for (int j = 0; j < 2; j++) {
            next_x += dx[dir_dust[i]];
            next_y += dy[dir_dust[i]];
            if (check_map_range(next_x, next_y) == true) {
                if (j == 0) {
                    A[next_x][next_y] += dust_total * 0.07;
                    alpah_dust -= int(dust_total * 0.07);
                }
                else if (j == 1) {
                    A[next_x][next_y] += dust_total * 0.02;
                    alpah_dust -= int(dust_total * 0.02);
                }
            }
            else {
                if (j == 0) {
                    alpah_dust -= int(dust_total * 0.07);
                }
                else if (j == 1) {
                    alpah_dust -= int(dust_total * 0.02);
                }
            }
            
        }
    }
    for (int i = 0; i < 2; i++) {
        int next_x = alpha_x + dx[dir_dust[i]];
        int next_y = alpha_y + dy[dir_dust[i]];
        if (check_map_range(next_x, next_y) == true) {
            A[next_x][next_y] += dust_total * 0.1;
        }
        alpah_dust -= int(dust_total * 0.1);
    }
    int next_x = alpha_x + dx[dir];
    int next_y = alpha_y + dy[dir];
    if (check_map_range(next_x, next_y) == true) {
        A[next_x][next_y] += dust_total * 0.05;
    }
    alpah_dust -= int(dust_total * 0.05);
    if (check_map_range(alpha_x, alpha_y) == true) {
        A[alpha_x][alpha_y] += alpah_dust;
    }
}
 
bool check_map_range(int& next_x, int& next_y){
    if (next_x >= 1 && next_x <= N && next_y >= 1 && next_y <= N) {
        return true;
    }
    return false;
}
 
 cs

코드를 줄이면 120? 까지도 줄일 수 있을거같지만 귀찮음..

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

[백준 14890] 경사로 (C++)  (0) 2021.08.20
[백준 19236] 청소년 상어 (C++)  (0) 2021.08.19
[백준 17837] 새로운 게임 2 (C++)  (0) 2021.08.17
[백준 2206] 벽 부수고 이동하기 (C++)  (0) 2021.08.16
[백준 17135] 캐슬 디펜스 (C++)  (0) 2021.08.16

재현이는 주변을 살펴보던 중 체스판과 말을 이용해서 새로운 게임을 만들기로 했다. 새로운 게임은 크기가 N×N인 체스판에서 진행되고, 사용하는 말의 개수는 K개이다. 말은 원판모양이고, 하나의 말 위에 다른 말을 올릴 수 있다. 체스판의 각 칸은 흰색, 빨간색, 파란색 중 하나로 색칠되어있다.

게임은 체스판 위에 말 K개를 놓고 시작한다. 말은 1번부터 K번까지 번호가 매겨져 있고, 이동 방향도 미리 정해져 있다. 이동 방향은 위, 아래, 왼쪽, 오른쪽 4가지 중 하나이다.

턴 한 번은 1번 말부터 K번 말까지 순서대로 이동시키는 것이다. 한 말이 이동할 때 위에 올려져 있는 말도 함께 이동한다. 말의 이동 방향에 있는 칸에 따라서 말의 이동이 다르며 아래와 같다. 턴이 진행되던 중에 말이 4개 이상 쌓이는 순간 게임이 종료된다.

  • A번 말이 이동하려는 칸이
    • 흰색인 경우에는 그 칸으로 이동한다. 이동하려는 칸에 말이 이미 있는 경우에는 가장 위에 A번 말을 올려놓는다.
      • A번 말의 위에 다른 말이 있는 경우에는 A번 말과 위에 있는 모든 말이 이동한다.
      • 예를 들어, A, B, C로 쌓여있고, 이동하려는 칸에 D, E가 있는 경우에는 A번 말이 이동한 후에는 D, E, A, B, C가 된다.
    • 빨간색인 경우에는 이동한 후에 A번 말과 그 위에 있는 모든 말의 쌓여있는 순서를 반대로 바꾼다.
      • A, B, C가 이동하고, 이동하려는 칸에 말이 없는 경우에는 C, B, A가 된다.
      • A, D, F, G가 이동하고, 이동하려는 칸에 말이 E, C, B로 있는 경우에는 E, C, B, G, F, D, A가 된다.
    • 파란색인 경우에는 A번 말의 이동 방향을 반대로 하고 한 칸 이동한다. 방향을 반대로 바꾼 후에 이동하려는 칸이 파란색인 경우에는 이동하지 않고 가만히 있는다.
    • 체스판을 벗어나는 경우에는 파란색과 같은 경우이다.

다음은 크기가 4×4인 체스판 위에 말이 4개 있는 경우이다.

첫 번째 턴은 다음과 같이 진행된다.

두 번째 턴은 다음과 같이 진행된다.

체스판의 크기와 말의 위치, 이동 방향이 모두 주어졌을 때, 게임이 종료되는 턴의 번호를 구해보자.

입력

첫째 줄에 체스판의 크기 N, 말의 개수 K가 주어진다. 둘째 줄부터 N개의 줄에 체스판의 정보가 주어진다. 체스판의 정보는 정수로 이루어져 있고, 각 정수는 칸의 색을 의미한다. 0은 흰색, 1은 빨간색, 2는 파란색이다.

다음 K개의 줄에 말의 정보가 1번 말부터 순서대로 주어진다. 말의 정보는 세 개의 정수로 이루어져 있고, 순서대로 행, 열의 번호, 이동 방향이다. 행과 열의 번호는 1부터 시작하고, 이동 방향은 4보다 작거나 같은 자연수이고 1부터 순서대로 →, ←, ↑, ↓의 의미를 갖는다.

같은 칸에 말이 두 개 이상 있는 경우는 입력으로 주어지지 않는다.

출력

게임이 종료되는 턴의 번호를 출력한다. 그 값이 1,000보다 크거나 절대로 게임이 종료되지 않는 경우에는 -1을 출력한다.

제한

  • 4 ≤ N ≤ 12
  • 4 ≤ K ≤ 10

예제 입력 1 

4 4
0 0 2 0
0 0 1 0
0 0 1 2
0 2 0 0
2 1 1
3 2 3
2 2 1
4 1 2

예제 출력 1 

-1

예제 입력 2 

4 4
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
1 1 1
1 2 1
1 3 1
1 4 1

예제 출력 2 

1

예제 입력 3 

4 4
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
1 1 1
1 2 1
1 3 1
2 4 3

예제 출력 3 

1

예제 입력 4 

4 4
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
1 1 1
1 2 1
1 3 1
3 3 3

예제 출력 4 

2

예제 입력 5 

6 10
0 1 2 0 1 1
1 2 0 1 1 0
2 1 0 1 1 0
1 0 1 1 0 2
2 0 1 2 0 1
0 2 1 0 2 1
1 1 1
2 2 2
3 3 4
4 4 1
5 5 3
6 6 2
1 6 3
6 1 2
2 4 3
4 2 1

예제 출력 5 

7

 

 

풀이

생각보다 쉬운문제였다.(물론 뇌절해서 4번?인가틀림)

각자 이동 할 chess 피스가 있는 층을 계산하고 어찌저찌 옮기면되는 문제

파란색과 경계밖일때는 같은방식.

move_white는 다음과 같다.

이동 해야 할 chess가 있는 곳을 cal_floor를 통해서 계산, 그리고 그 위에있는 것을 모두 잘라 이동.

move_red도 비슷한 방식

이동 해야 할 chess가 있는 곳을 cal_floor를 통해서 계산, 그리고 그 위에있는 것을 스택에 넣어서 이동

blue인 경우와 벽인 경우는 

방향을 change 한 뒤에 next_x와 next_y의 위치를 다시 계산,red나 빈공간이면 move_white,red 함수 호출

전체 코드는 다음과 같다.

move_blue도 함수로 만들려 했지만 귀차니즘과 &로 인한 오류로 인해그냥 쳐박아버린..

이거 해결시 https://www.acmicpc.net/problem/17780 이것도 꽁자로 해결

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
#include <iostream>
#include <vector>
#include <deque>
#include <algorithm>
#include <stack>
#define MAX 12+1
using namespace std;
// Chess_piece 구조체
struct Chess_piece
{
    int x, y;
    int dir;
    int num;
};
// 맵 크기, 말 개수
int N, K;
// 방향 →, ←, ↑, ↓
int dx[5] = { 0, 0,0,-1,1 };
int dy[5] = { 0, 1,-1,0,0 };
// 0 1 2, 흰색 빨간색 파란색 MAP
int map_color[MAX][MAX];
// Chess_piece 정보 저장
Chess_piece Chess_MAP[MAX];
// 쌓인 모양
deque<int> MAP[MAX][MAX];
void print() {
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            cout << MAP[i][j].size() << " ";
        }
        cout << endl;
    }
}
int cal_floor(int& index, int& size_MAP, int& pre_x, int& pre_y) {
    for (int i = 0; i < size_MAP; i++)
        if (MAP[pre_x][pre_y][i] == Chess_MAP[index].num)
            return i;
}
void move_red(int& pre_x, int& pre_y, int& i, int& next_x, int& next_y) {
    int size_MAP = MAP[pre_x][pre_y].size();
    int floor = cal_floor(i, size_MAP, pre_x, pre_y);
    stack<int> temp;
    // 이동할 것들 저장
    for (int j = floor; j < size_MAP; j++) {
        temp.push(MAP[pre_x][pre_y][j]);
    }
    while (!temp.empty()) {
        MAP[pre_x][pre_y].pop_back();
        MAP[next_x][next_y].push_back(temp.top());
        Chess_MAP[temp.top()].x = next_x;
        Chess_MAP[temp.top()].y = next_y;
        temp.pop();
    }
}
void move_white(int& pre_x, int& pre_y, int& i, int& next_x, int& next_y) {
    int size_MAP = MAP[pre_x][pre_y].size();
    int floor = cal_floor(i, size_MAP, pre_x, pre_y);
    vector<int> temp;
    // 이동할 것들 저장
    for (int j = floor; j < size_MAP; j++)
        temp.push_back(MAP[pre_x][pre_y][j]);
    // 이동
    for (auto j : temp) {
        MAP[pre_x][pre_y].pop_back();
        MAP[next_x][next_y].push_back(j);
        Chess_MAP[j].x = next_x;
        Chess_MAP[j].y = next_y;
    }
}
 
void solve() {
    int count = 1;
    while (1) {
        if (count > 1000) {
            cout << -1 << endl;
            break;
        }
        for (int i = 1; i <= K; i++) {
            int pre_x = Chess_MAP[i].x;
            int pre_y = Chess_MAP[i].y;
            int next_x = pre_x + dx[Chess_MAP[i].dir];
            int next_y = pre_y + dy[Chess_MAP[i].dir];
            if (next_x >= 1 && next_x <= N && next_y >= 1 && next_y <= N) {
                if (map_color[next_x][next_y] == 0) {
                    move_white(pre_x, pre_y, i, next_x, next_y);
                }
                else if (map_color[next_x][next_y] == 1) {
                    move_red(pre_x, pre_y, i, next_x, next_y);
                }
                else if (map_color[next_x][next_y] == 2) {
                    if (Chess_MAP[i].dir == 1)
                        Chess_MAP[i].dir = 2;
                    else if (Chess_MAP[i].dir == 2)
                        Chess_MAP[i].dir = 1;
                    else if (Chess_MAP[i].dir == 3)
                        Chess_MAP[i].dir = 4;
                    else if (Chess_MAP[i].dir == 4)
                        Chess_MAP[i].dir = 3;
                    next_x = pre_x + dx[Chess_MAP[i].dir];
                    next_y = pre_y + dy[Chess_MAP[i].dir];
                    if (next_x >= 1 && next_x <= N && next_y >= 1 && next_y <= N) {
                        if (map_color[next_x][next_y] == 0) {
                            move_white(pre_x, pre_y, i, next_x, next_y);
                        }
                        else if (map_color[next_x][next_y] == 1) {
                            move_red(pre_x, pre_y, i, next_x, next_y);
                        }
                    }
                }
            }
            else {
                if (Chess_MAP[i].dir == 1)
                    Chess_MAP[i].dir = 2;
                else if (Chess_MAP[i].dir == 2)
                    Chess_MAP[i].dir = 1;
                else if (Chess_MAP[i].dir == 3)
                    Chess_MAP[i].dir = 4;
                else if (Chess_MAP[i].dir == 4)
                    Chess_MAP[i].dir = 3;
                next_x = pre_x + dx[Chess_MAP[i].dir];
                next_y = pre_y + dy[Chess_MAP[i].dir];
                if (next_x >= 1 && next_x <= N && next_y >= 1 && next_y <= N) {
                    if (map_color[next_x][next_y] == 0) {
                        move_white(pre_x, pre_y, i, next_x, next_y);
                    }
                    else if (map_color[next_x][next_y] == 1) {
                        move_red(pre_x, pre_y, i, next_x, next_y);
                    }
                }
            }
            for (int num_ = 1; num_ <= K; num_++) {
                if (MAP[Chess_MAP[num_].x][Chess_MAP[num_].y].size() >= 4) {
                    cout << count << endl;
                    return;
                }
            }
        }
        count++;
    }
}
void input() {
    cin >> N >> K;
    for (int i = 1; i <= N; i++)
        for (int j = 1; j <= N; j++)
            cin >> map_color[i][j];
    for (int i = 1; i <= K; i++) {
        int x, y, dir;
        cin >> x >> y >> dir;
        Chess_MAP[i] = { x,y,dir,i };
        MAP[x][y].push_back(i);
    }
}
// init 함수
void init() {
    ios::sync_with_stdio(false);
    cin.tie(0);
}
int main() {
    init();
    input();
    solve();
}
 cs

 

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

[백준 19236] 청소년 상어 (C++)  (0) 2021.08.19
[백준 20057] 마법사 상어와 토네이도 (C++)  (0) 2021.08.18
[백준 2206] 벽 부수고 이동하기 (C++)  (0) 2021.08.16
[백준 17135] 캐슬 디펜스 (C++)  (0) 2021.08.16
[백준 17140] 이차원 배열과 연산 (C++)  (0) 2021.08.13

+ Recent posts

티스토리툴바