반응형

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

 

 

[ 문제풀이 ]

 

1. 냄새를 남길 수 있게 smell struct를 만들어 상어의 번호와 남은 시간을 저장합니다.

 

2. 상어의 위치를 shark struct를 만들어 현재 좌표와 방향을 저장합니다.

 

3. arr 배열을 통해서 현재 상어의 위치 상태를 확인합니다.

 

4. 상어가 먼저 냄새를 남깁니다.

 

5. 규칙에 따라 이동해줍니다. 여기서 이동할 수 있는 모든 방향에 냄새가 있다면 이동 우선순위에 따라서 본인의 냄새가 있던 곳으로 이동해 주어야 합니다.

 

6. 1번 상어가 남을 때까지 위 과정을 반복하고, 1번 상어만 남았을 때는 걸린 시간을 출력해줍니다.

 

7. 만약 1000초가 넘어도 1번 상어만 남지 않을 경우 -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
#include<iostream>
 
using namespace std;
 
struct shark {        //상어의 상태
    int y;
    int x;
    int dir;
};
 
struct smell {        //냄새 주인과 남은 시간
    int num;
    int k;
};
 
int N, M, k;
int dy[5] = { 0,-1,1,0,0 };
int dx[5] = { 0,0,0,-1,1 };
int arr[20][20];
int priority[401][5][4];
smell map[20][20];
shark pos[401];
 
void move()        //상어 움직임
{
    for (int i = 1; i <= M; i++) {
        bool flag = false;
        if (pos[i].y != -1) {
            for (int j = 0; j < 4; j++) {
                int dir = priority[i][pos[i].dir][j];
                int yy = pos[i].y + dy[dir];
                int xx = pos[i].x + dx[dir];
                if (yy >= 0 && yy < N && xx >= 0 && xx < N) {
                    if (map[yy][xx].num == 0) {    //냄새가 없는 장소가 있다면
                        arr[pos[i].y][pos[i].x] = 0;
                        if (arr[yy][xx] == 0) {    //그 장소에 아무도 없다면
                            pos[i] = { yy,xx,dir };
                            arr[yy][xx] = i;
                        }
                        else if (arr[yy][xx] < i) {    //그 장소에 나보다 센 상어가 있다면
                            pos[i] = { -1,-1,-1 };
                        }
                        else if (arr[yy][xx] > i){    //그 장소에 나보다 약한 상어가 있다면
                            pos[arr[yy][xx]] = { -1,-1,-1 };
                            pos[i] = { yy,xx,dir };
                            arr[yy][xx] = i;
                        }
                        flag = true;
                        break;
                    }
                }
            }
            if (flag == false) {    //냄새가 모두 둘러싸고 있다면
                for (int j = 0; j < 4; j++) {
                    int dir = priority[i][pos[i].dir][j];
                    int yy = pos[i].y + dy[dir];
                    int xx = pos[i].x + dx[dir];
                    if (yy >= 0 && yy < N && xx >= 0 && xx < N) {
                        if (map[yy][xx].num == i) {    //나의 냄새가 있는 곳으로
                            arr[pos[i].y][pos[i].x] = 0;
                            pos[i] = { yy,xx,dir };
                            arr[yy][xx] = i;
                            break;
                        }
                    }
                }
            }
        }
    }
}
 
void smells()
{
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if (map[i][j].num != 0) {
                map[i][j].k--;
                if (map[i][j].k == 0) {
                    map[i][j].num = 0;
                }
            }
        }
    }
 
    for (int i = 1; i <= M; i++) {
        if (pos[i].y != -1) {
            map[pos[i].y][pos[i].x] = { i, k };
        }
    }
}
 
int main()
{
    scanf("%d %d %d", &N, &M, &k);
 
    for (int i = 0; i < N; i++)    {
        for (int j = 0; j < N; j++) {
            scanf("%d", &arr[i][j]);
            pos[arr[i][j]] = { i,j };
        }
    }
 
    for (int i = 1; i <= M; i++) {
        int dir;
        scanf("%d", &dir);
 
        pos[i].dir = dir;
    }
 
    for (int i = 1; i <= M; i++) {
        for (int j = 1; j <= 4; j++) {
            for (int k = 0; k < 4; k++) {
                int dir;
                scanf("%d", &dir);
 
                priority[i][j][k] = dir;
            }
        }
    }
 
    int ans = 0;
 
    while (1) {
        ans++;
        smells();
 
        move();
 
        int cnt = 0;
 
        for (int i = 1; i <= M; i++) {
            if (pos[i].y != -1) {
                cnt++;
            }
        }
 
        if (cnt == 1) {    //1번 상어만 남는다면
            printf("%d", ans);
            return 0;
        }
 
        if (ans == 1000) {    //1000번을 넘으면
            printf("%d", -1);
            return 0;
        }
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 21609번 - 상어 중학교 (C++)  (0) 2022.10.02
[ 백준 ] 19238번 - 스타트 택시 (C++)  (0) 2022.10.01
[ 백준 ] 19236번 - 청소년 상어 (C++)  (0) 2022.09.29
[ 백준 ] 20061번 - 모노미노도미노 2 (C++)  (0) 2022.09.28
[ 백준 ] 17825번 - 주사위 윷놀이 (C++)  (0) 2022.09.27

+ Recent posts

티스토리툴바