baekjoon 16236:아기 상어
16236번 아기 상어
접근
bfs돌리는건데 좀 까다로운 규칙이 있는 정도이다.
같은 거리 애들 중 가장 위, 가장 왼쪽에 있는 물고기를 먹어야하니 k level나눠서 도는
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
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
#include <iostream>
#include <vector>
#include <array>
#include <queue>
#include <algorithm>
using namespace std;
void search(int dx, int dy, pair<int, int> curr, vector<vector<int>>& g, vector<vector<int>>& dist, vector<pair<int, int>>& v, queue<pair<int, int>>& q, int size);
int main(){
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int n; cin >> n;
vector<vector<int>> g(n, vector<int>(n));
pair<int, int> start;
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
cin >> g[i][j];
if(g[i][j] == 9){
start = {i, j};
}
}
}
int size = 2;
int eat = 0;
int time = 0;
//bfs 돌리면 됨
//어짜피 1개 있어도 가장 먼저 발견한거 먹을거니까
//먹을 수 있는 거 발견 못하고 queue끝나면 끝
//찾으면 그 위치로 이동, 거리만큼 초 추가
//그 위치에서 다시 bfs 돌려서 먹을 수 있는지 확인 while함수사용
//위, 왼쪽 순으로 탐색
while(true){
//bfs돌리기
int initEat = eat;
pair<int, int> initStart = start;
queue<pair<int, int>> q;
q.push(start);
vector<vector<int>> dist(n, vector<int>(n, -1));
dist[start.first][start.second] = 0;
while(!q.empty()){
vector<pair<int, int>> v;
int qsize = q.size();
//저장 안하고 돌리면 매 i마다 다시 q.size()호출함
for(int i = 0; i < qsize; i++){
pair<int, int> curr = q.front();
q.pop();
search(-1, 0, curr, g, dist, v, q, size);
search(0, -1, curr, g, dist, v, q, size);
search(1, 0, curr, g, dist, v, q, size);
search(0, 1, curr, g, dist, v, q, size);
}
sort(v.begin(), v.end());
if(!v.empty()){
start = v[0];
eat++;
break;
}
}
if(initEat + 1 == eat){
g[start.first][start.second] = 9;
g[initStart.first][initStart.second] = 0;
time += dist[start.first][start.second];
if(eat == size){
size++;
eat = 0;
}
}
else if(eat == initEat){
break;
}
}
cout << time;
return 0;
}
void search(int dy, int dx, pair<int, int> curr, vector<vector<int>>& g, vector<vector<int>>& dist, vector<pair<int, int>>& v, queue<pair<int, int>>& q, int size){
if(curr.first+dy >= 0 && curr.first+dy < g.size() && curr.second + dx >= 0 && curr.second + dx < g.size() && g[curr.first+dy][curr.second+dx] <= size && dist[curr.first+dy][curr.second+dx] == -1){
dist[curr.first+dy][curr.second+dx] = dist[curr.first][curr.second] + 1;
if(g[curr.first+dy][curr.second+dx] != 0 && g[curr.first+dy][curr.second+dx] < size){
v.push_back({curr.first+dy, curr.second+dx});
}
q.push({curr.first+dy, curr.second+dx});
}
}
배운 점
for문에서 i<q.size()라 하면 돌 때마다 계속 호출해서 업데이트 된다. 무조건 처음 저장하고 해야한다.
This post is licensed under CC BY 4.0 by the author.