Post

baekjoon 16236:아기 상어

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.