16236, Gold 4

16236번: 아기 상어

문제

• 아기상어의 초기크기는 2, |본인| 마리수의 물고기를 먹으면 사이즈+1
• 먹을 수 있는 것 : |본인| > |물고기|
• 지나갈 수 있는 칸: |본인| ≥ |물고기| 
• 먹이 우선순위 :
  1. 거리가 가깝다
  2. 위쪽에 있다
  3. 왼쪽에 있다

 

풀이

가중치가 없는 그래프이므로 bfs 를 사용하면 된다. 이때 다음만 주의해주면 된다

1. 움직이려는 칸이 좌표 유효?
   0 ≤ row < n & 0 ≤ column < n
2. 움직이려는 칸이 size 이하?
   이때 아기상어 초기좌표값 9를 지워준다. 혹은 따로 처리해주어야 한다
3. 움직이려는 칸이 방문하지 않았는지?
4. 당연히 먹었으면 물고기는 좌표상에서 없애야 한다
5. 먹이 우선순위 충족여부
   

   

   처음엔 queue 를 이용하여 위와같이 bfs 하면
   가장 처음 닿는 물고기가 우선순위를 충족할 것이라 생각했으나 그렇지 않았다. 아래는 반례
   

   

c++

#include <bits/stdc++.h>
#define endl "\n"
#define ooop(i, n) for(int i = 0; i < n; i++)
#define loop(i, n) for(int i = 1; i <= n; i++)
 
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
 
int n;
int shark_size = 2;
int experience = 2;
 
struct info{
    int r;
    int c;
    int t;
};
 
info find_fish(int shark_r, int shark_c, vector<vector<int> >& d)
{
    vector<vector<int> > visited(n, vector<int>(n));
    queue<info> q;
    q.push({shark_r, shark_c, 0});
    visited[shark_r][shark_c] = 1;
 
    int food_dist = 0;
    vector<pii> food;
    while(!q.empty()){
        auto [cr, cc, ct] = q.front(); q.pop();
 
        if(food_dist){
            if(d[cr][cc] > 0  && d[cr][cc] < shark_size && ct == food_dist) food.push_back({cr, cc});
            continue;
        }
        else{
            if(d[cr][cc] > 0  && d[cr][cc] < shark_size){
                food.push_back({cr, cc});
                food_dist = ct;
                continue;
            }
        }
 
        ooop(i, 4){
            int nr = cr + "0112"[i] - '1', nc = cc + "1021"[i] - '1';
            if(nr < 0 || nr >= n || nc < 0 || nc >= n) continue;
            if(d[nr][nc] <= shark_size && visited[nr][nc] == 0){
                q.push({nr, nc, ct+1});
                visited[nr][nc] = 1;
            }
        }
    }
 
    if(!food.empty()){
        sort(food.begin(), food.end());
        tie(shark_r, shark_c) = food[0];
    }
    info rut = {shark_r, shark_c, food_dist};
    return rut;
}
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
 
    cin >> n;
    vector<vector<int> > d(n, vector<int>(n));
 
    int shark_r, shark_c;
    ooop(r, n){
        ooop(c, n) {
            cin >> d[r][c];
            if(d[r][c] == 9){ shark_r = r; shark_c = c;}
        }
    }
    d[shark_r][shark_c] = 0;
 
    int time = 0;
    while(true){
        auto i = find_fish(shark_r, shark_c, d);
        if(i.r != shark_r || i.c != shark_c) {
            d[i.r][i.c] = 0;
            shark_r = i.r; shark_c = i.c;
            if(experience > 1) experience--;
            else{
                shark_size++;
                experience = shark_size;
            }
            time += i.t;
        }
        else break;
    }
 
    cout << time << endl;
 
    return 0;
}cs

python 3

import sys
from collections import defaultdict as dd
 
def distance(shark):
    q = [shark]
    dis = 0
    m = [[401]*n for _ in range(n)]
    m[shark[0]][shark[1]] = 0
    while 1:
        dis += 1
        q_ = []
        for cr, cc in q:
            for dr, dc in [(-1, 0), (0, 1), (1, 0), (0, -1)]:
                nr, nc = cr+dr, cc+dc
                if 0 <= nr < n and 0 <= nc < n and m[nr][nc] == 401 and d[nr][nc] <= size:
                    m[nr][nc] = dis
                    q_.append((nr, nc))
        if q_: q = q_
        else: break
    return m
 
n = int(input())
d = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]
fish = dd(set)
for r in range(n):
    for c in range(n):
        if d[r][c] != 0: fish[d[r][c]].add((r, c, d[r][c]))
time = 0
size = 2
eat = 0
cr, cc, _ = fish[9].pop()
d[cr][cc] = 0
while "eating":
    smaller = set().union(*map(lambda s: fish[s], filter(lambda i: i < size, range(7))))
    m = distance((cr, cc))
    eatable = sorted(filter(lambda i: i[0] < 401, [(m[e[0]][e[1]], *e) for e in smaller]))
    if len(eatable) == 0: break
    dis, cr, cc, target_size = eatable[0]
    time += dis
    eat += 1
    fish[target_size].remove((cr, cc, target_size))
    if eat == size:
        size += 1
        eat = 0
print(time)cs

 

디버깅(data visualization)

탐색문제는 데이터 양이 많아서 본인은 디버거만으로 디버깅하기 어렵다고 생각한다

data_visualiztion.py

import sys
import matplotlib.pyplot as plt
 
f = open("data_visualization", 'r')
data = f.read().split("\n\n")
f.close()
 
for fig_num, d in enumerate(data):
    d = list(map(lambda row: list(map(int, list(row))), d.split()))
    plt.figure(figsize=(5, 5))
    plt.imshow(d)
    plt.show()
    #plt.savefig(f"{fig_num}")cs