반응형

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

 

23290번: 마법사 상어와 복제

첫째 줄에 물고기의 수 M, 상어가 마법을 연습한 횟수 S가 주어진다. 둘째 줄부터 M개의 줄에는 물고기의 정보 fx, fy, d가 주어진다. (fx, fy)는 물고기의 위치를 의미하고, d는 방향을 의미한다. 방향

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. fish struct를 만들어 vector <fish> vect에 물고기의 좌표와 방향을 저장하고, cnt 배열에 물고기의 개수를 저장합니다.

 

2. temp 배열에 물고기의 현재 위치를 저장하고, 물고기를 이동시키고, cnt 배열을 갱신해줍니다.

 

3. dfs를 이용하여 상어를 이동시키고, 이동한 좌표들을 box 배열에 저장합니다.

 

3. for문을 이용하여 vect 배열을 탐색하면서 상어가 지나간 자리에 있었던 물고기들의 좌표를 0으로 바꿔주고, 냄새를 남기고, 해당 좌표의 cnt 배열의 값을 0으로 경신합니다.

 

5. 냄새를 1 깎아줍니다.

 

6. temp 배열에 있는 물고기들의 좌표를 이용하여 cnt 배열을 갱신해주고, temp 배열에 남아있는 물고기들을 push 해줍니다.

 

7. vect 배열을 temp 배열로 초기화해줍니다.

 

8. 위 과정을 반복합니다.

 

[ 소스코드 ]

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
#include<iostream>
#include<vector>
 
using namespace std;
 
struct fish{
    int y;
    int x;
    int d;
};
 
int M, S;
int arr[5][5];    //상어 위치
int smell[5][5];    //냄새 위치
vector<fish> vect;
int fy[9] = { 0,0,-1,-1,-1,0,1,1,1 };    //물고기 방향 배열
int fx[9] = { 0,-1,-1,0,1,1,1,0,-1 };
int dy[4] = { -1,0,1,0 };        //상어 방향 배열
int dx[4] = { 0,-1,0,1 };
int cnt[5][5];    //물고기 수
int sy, sx;        //상어 좌표
pair<int,int> temp[3];
pair<int,int> box[3];
int Max;
 
void dfs(int y, int x, int level, int ans)    //상어 이동
{
    if (level == 3) {
        if (Max < ans) {
            Max = ans;
            for (int i = 0; i < 3; i++) {
                box[i] = temp[i];
            }
        }
        return;
    }
 
    for (int i = 0; i < 4; i++) {
        int yy = y + dy[i];
        int xx = x + dx[i];
        if (yy > 0 && yy <= 4 && xx > 0 && xx <= 4) {
            temp[level] = { yy,xx };
            int temp = cnt[yy][xx];
            cnt[yy][xx] = 0;
            dfs(yy, xx, level + 1, ans + temp);
            cnt[yy][xx] = temp;
        }
    }
}
 
void move()        //물고기 이동
{
    for (auto &next : vect) {
        int y = next.y;
        int x = next.x;
        int d = next.d;
        for (int i = 0; i < 8; i++) {
            int yy = y + fy[d];
            int xx = x + fx[d];
            if (yy > 0 && yy <= 4 && xx > 0 && xx <= 4) {
                if (arr[yy][xx] == 0 && smell[yy][xx] == 0) {
                    next.y = yy;
                    next.x = xx;
                    next.d = d;
                    cnt[y][x]--;
                    cnt[yy][xx]++;
                    break;
                }
            }
            d--;
            if (d <= 0) {
                d += 8;
            }
        }
    }
}
 
int main()
{
    scanf("%d %d", &M, &S);
 
    for (int i = 0; i < M; i++) {
        int y, x, d;
        scanf("%d %d %d", &y, &x, &d);
        vect.push_back({ y,x,d });
        cnt[y][x]++;
    }
 
    scanf("%d %d", &sy, &sx);
 
    arr[sy][sx] = 5;
 
    for(int s=0;s<S;s++){
        vector<fish> temp = vect;
 
        move();
 
        Max = -1;
 
        dfs(sy, sx, 0, 0);
        arr[sy][sx] = 0;
        sy = box[2].first;
        sx = box[2].second;
        arr[sy][sx] = 5;
 
        for (int i = 0; i < 3; i++) {
            cnt[box[i].first][box[i].second] = 0;
        }
 
        for (int i = 0; i < vect.size(); i++) {
            for (int j = 0; j < 3; j++) {
                if (vect[i].y == box[j].first && vect[i].x == box[j].second) {
                    smell[vect[i].y][vect[i].x] = 3;
                    cnt[vect[i].y][vect[i].x] = 0;
                    vect[i].y = 0;
                    break;
                }
            }
        }
 
        for (int i = 1; i <= 4; i++) {
            for (int j = 1; j <= 4; j++) {
                if (smell[i][j] > 0) {
                    smell[i][j]--;
                }
            }
        }
 
        for (int i = 0; i < temp.size(); i++) {
            cnt[temp[i].y][temp[i].x]++;
        }
 
        for (int i = 0; i < vect.size(); i++) {
            if (vect[i].y != 0) {
                temp.push_back({ vect[i].y, vect[i].x, vect[i].d });
            }
        }
 
        vect = temp;
    }
 
    printf("%d", vect.size());
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

'백준' 카테고리의 다른 글

[ 백준 ] 17281번 - ⚾ (C++)  (0) 2022.10.07
[ 백준 ] 17136번 - 색종이 붙이기 (C++)  (0) 2022.10.06
[ 백준 ] 23289번 - 온풍기 안녕! (C++)  (0) 2022.10.04
[ 백준 ] 23288번 - 주사위 굴리기 2 (C++)  (0) 2022.10.03
[ 백준 ] 21609번 - 상어 중학교 (C++)  (0) 2022.10.02

+ Recent posts

티스토리툴바