알고리즘 문제풀이/백준
[백준 19237번] 어른 상어
슥지니
2022. 4. 4. 03:52
반응형
문제 링크: 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
<문제 풀이> BFS
이문제는 상어의 방향 정보를 클래스로 묶어서 관리하면 간단하게 해결할 수 있습니다.
그런데 주의할 점은 상어가 이동할 때 여러 상어가 겹치는 부분을 처리해야 하는데 이때 상어를 한 마리씩 이동시킬 때 바로 이동 상태를 맵에 반영하는 게 아니라 임시 큐를 하나 생성해서 임시로 이동시킨 후 번호가 낮은 상어만 맵에 반영해야 합니다.
그리고 또 주의할 점 하나는 시간이 1000초 일 때 상어가 2마리 이상이면 -1을 리턴해야합니다.
<C++ 소스 코드>
|
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>
#include<queue>
#include<utility>
#include<algorithm>
using namespace std;
#define X first
#define Y second
#define NUM first
#define SMELL second
class shark {
public:
int curDir;
int nextDir[5][5];
void del() {
curDir = -1;
}
bool exist() {
return curDir != -1;
}
};
shark info[401];
int N, M, K;
int board[20][20];
pair<int, int> visited[20][20];
queue<pair<int, int > > Q;
const int dx[5] = {0, -1, 1, 0, 0};
const int dy[5] = {0, 0 , 0, -1, 1};
int tot_shark;
void decreaseSMELL() {
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (visited[i][j].SMELL && !board[i][j]) {
visited[i][j].SMELL--;
}
}
}
}
int bfs() {
int t = 0;
while (!Q.empty()) {
int Q_size = Q.size();
queue<pair<int, int> > tempQ; //임시로 다음 상어를 이동 시킴
queue<int> num; //임시로 이동 시킨 상어의 번호
for (int i = 0; i < Q_size; i++) {
auto cur = Q.front(); Q.pop();
if (!info[board[cur.X][cur.Y]].exist())continue;
bool flag = false; //냄새가 없는 곳을 찾으면 true
for (int dir = 1; dir <= 4; dir++) {
shark s = info[board[cur.X][cur.Y]];
int nx = cur.X + dx[s.nextDir[s.curDir][dir]];
int ny = cur.Y + dy[s.nextDir[s.curDir][dir]];
if (nx < 0 || ny < 0 || nx >= N || ny >= N) continue;
if (visited[nx][ny].SMELL)continue;
Q.push({ nx, ny });
tempQ.push({ nx, ny });
num.push(board[cur.X][cur.Y]);
info[board[cur.X][cur.Y]].curDir = s.nextDir[s.curDir][dir];
board[cur.X][cur.Y] = 0;
flag = true;
break;
}
if (!flag) { // 만약 냄새가 없는 곳이 없으면 자기 냄새가 있는 공간을 찾아서 이동
for (int dir = 1; dir <= 4; dir++) {
shark s = info[board[cur.X][cur.Y]];
int nx = cur.X + dx[s.nextDir[s.curDir][dir]];
int ny = cur.Y + dy[s.nextDir[s.curDir][dir]];
if (nx < 0 || ny < 0 || nx >= N || ny >= N) continue;
if (visited[nx][ny].NUM == visited[cur.X][cur.Y].NUM) {
tempQ.push({ nx, ny });
Q.push({ nx, ny });
num.push(board[cur.X][cur.Y]);
info[board[cur.X][cur.Y]].curDir = s.nextDir[s.curDir][dir];
board[cur.X][cur.Y] = 0;
flag = true;
break;
}
}
}
}
while (!tempQ.empty()) {
auto cur = tempQ.front(); tempQ.pop();
int n = num.front(); num.pop();
if (board[cur.X][cur.Y]) { //상어가 겹치면
if (n < board[cur.X][cur.Y]) { // 더 작은 번호의 상어만 살아 남는다
info[board[cur.X][cur.Y]].del();
board[cur.X][cur.Y] = n;
visited[cur.X][cur.Y].SMELL = K;
visited[cur.X][cur.Y].NUM = n;
}
tot_shark--; //상어 한 마리 죽이기
}
else {
board[cur.X][cur.Y] = n;
visited[cur.X][cur.Y].SMELL = K;
visited[cur.X][cur.Y].NUM = n;
}
}
decreaseSMELL();
t++;
if (tot_shark == 1) return t;
if (t >= 1000) return -1;
}
}
int main(void) {
ios_base::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
cin >> N >> M >> K;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
cin >> board[i][j];
if (board[i][j] != 0) {
visited[i][j].NUM = board[i][j];
visited[i][j].SMELL = K;
Q.push({ i, j });
tot_shark++;
}
}
}
for (int i = 1; i <= M; i++) {
cin >> info[i].curDir;
}
for (int i = 1; i <= M; i++) {
for (int j = 1; j <= 4; j++) {
cin >> info[i].nextDir[j][1];
cin >> info[i].nextDir[j][2];
cin >> info[i].nextDir[j][3];
cin >> info[i].nextDir[j][4];
}
}
info[0].del();
cout<<bfs();
return 0;
}
|
cs |
반응형