(BOJ) 16236 아기 상어

문제: https://www.acmicpc.net/problem/16236

문제 풀이:

1. bfs를 이용하여 가장 가까운 물고기 위치와 거기까지의 거리 구함

1-1) 먹을 수 있는 물고기 중 가장 가까운 거리에 있는 곳들을 저장

1-2) sort해서 가장 위, 왼쪽인 것을 고른다.

2. 현재 먹은 물고기 수가 상어의 크기와 같으면 -> 상어 크기++, 현재 먹은 물고기 수= 0

   

* 처음에는 "상좌우하" 순으로 탐색해서 먹을 수 있는 물고기 발견 즉시 거기로 이동했다 

  그러면 예제4번의 답이 제대로 나오지 않는다.

  (0,2)에서 (0,4)로 이동해야 하는데 (1,1)로 이동 함

-> 거리가 최소로 같은 물고기들 저장하고 제일 위이면서 왼쪽인 것 골라서 가야한다.

소스코드:

#include <iostream> #include <queue> #include <vector> #include <string> #include <string.h> #include <tuple> #include <algorithm> #define inf 987654321 using namespace std; typedef pair<int, int> P; int n,arr[21][21],a,b,t,res; int dx[4] = { -1,0,0,1 }; int dy[4] = { 0,-1,1,0 }; bool visit[21][21]; bool bfs(int x, int y,int sz) { memset(visit, false, sizeof(visit)); queue<pair<int,pair<int,int>>> q; vector<pair<int, pair<int, int>>> v; bool check = false; q.push({ 0,{ x,y } }); while (!q.empty()) { t = q.front().first; int cur_x = q.front().second.first; int cur_y = q.front().second.second; q.pop(); if (!v.empty() && v[0].first < t + 1) break; for (int i = 0; i < 4; i++) { int xx = cur_x + dx[i]; int yy = cur_y + dy[i]; if (xx < 0 || xx >= n || yy < 0 || yy >= n||visit[xx][yy]||arr[xx][yy]>sz) continue; visit[xx][yy] = true; if (arr[xx][yy]<sz&&arr[xx][yy]!=0) { a = xx; b = yy; v.push_back({ t + 1,{a,b} }); check = true; continue; } q.push({ t + 1,{ xx,yy } }); } } if (check) { sort(v.begin(), v.end()); t = v[0].first; a = v[0].second.first; b = v[0].second.second; return true; } return false; } void func(int x, int y, int sz, int cnt) { if (!bfs(x, y, sz)) return; res += t ; arr[a][b] = 0; if (cnt + 1 == sz) func(a, b, sz + 1, 0); else func(a, b, sz, cnt + 1); } int main() { ios::sync_with_stdio(false); cin.tie(NULL), cout.tie(NULL); cin >> n; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { cin >> arr[i][j]; if (arr[i][j] == 9) {  arr[i][j] = 0; a = i; b = j; } } } func(a, b, 2, 0); cout << res<<'\n'; return 0; }