boj 16236 아기 상어

www.acmicpc.net/problem/16236

16236번: 아기 상어

상어가 지나갈 수 있는 경우는

1. 자신의 크기보다 작거나 같은 물고기가 있는 경우

2. 빈 칸

이렇게 두 가지이며, 상어는 자신보다 작은 물고기만 먹을 수 있습니다.

그리고 자신의 크기와 같은 수의 물고기를 먹으면 크기가 1 커집니다.

 

상어가 먹을 수 있는 물고기를 bfs로 찾고,

먹을 수 있는 물고기가 여러마리면 그 중 가장 가까운 물고기, 가장 위에 있는 물고기, 가장 왼쪽에 있는 물고기 순으로 먹습니다.

 

저는 bfs로 순회하며 먹을 수 있는 물고기를 ArrayList에 담았고 위의 조건 순으로 정렬하였습니다.

그럼 0번 인덱스에 있는 물고기를 먹으면 되고, 그 물고기까지의 거리를 ans에 더해주고, 그 위치에서 다시 시작합니다.

위의 과정을 물고기를 먹을 수 있을때까지 반복해줍니다.

 

 

[C++]

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;
 
queue<pair<int, int> > q;
int list[21][21];
bool visit[21][21];
int direct[4][2] = { {0,1},{1,0},{0,-1},{-1,0} };
int N, ans;
 
bool cmp(pair<int, int> a, pair<int, int> b) {
    if (a.first < b.first) return true;
    else if (a.first == b.first) {
        if (a.second < b.second) return true;
        else return false;
    }
    else return false;
}
 
void bfs() {
    int ssize = 2;
    int eat = 0;
    while (1) {
        bool chk = false;
        vector<pair<int, int> > v;
        for (int t = 1; ; t++) {
            int qsize = q.size();
            while (qsize--) {
                int x = q.front().first;
                int y = q.front().second;
                q.pop();
 
                for (int i = 0; i < 4; i++) {
                    int nx = x + direct[i][0];
                    int ny = y + direct[i][1];
 
                    if (nx < 0 || ny < 0 || nx >= N || ny >= N) continue;
                    if (visit[nx][ny]) continue;
                    if (list[nx][ny] > ssize) continue;
 
                    if (list[nx][ny] && list[nx][ny] < ssize) {
                        v.push_back({ nx,ny });
                    }
                    q.push({ nx,ny });
                    visit[nx][ny] = true;
                }
            }
 
            if (!v.empty()) {
                ans += t;
                break;
            }
            if (q.empty()) {
                chk = true;
                break;
            }
        }
        if (chk) break;
 
        sort(v.begin(), v.end(), cmp);
        int x = v[0].first;
        int y = v[0].second;
        list[x][y] = 0;
        eat++;
        if (eat == ssize) {
            ssize++;
            eat = 0;
        }
        v.clear();
        memset(visit, false, sizeof(visit));
        while (!q.empty()) q.pop();
        q.push({ x,y });
        visit[x][y] = true;
    }
 
    cout << ans << '\n';
}
 
void input() {
    cin >> N;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cin >> list[i][j];
            if (list[i][j] == 9) {
                q.push({ i,j });
                visit[i][j] = true;
                list[i][j] = 0;
            }
        }
    }
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    input();
    bfs();
 
    return 0;
}

 

 

[Java]

import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.Deque;
import java.util.StringTokenizer;
import java.io.BufferedReader;
 
public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static Deque<int[]> dq = new ArrayDeque<>();
    static int list[][] = new int[21][21];
    static boolean visit[][] = new boolean[21][21];
    static int direct[][] = { { 0, 1 }, { 1, 0 }, { 0, -1 }, { -1, 0 } };
    static int N, ans;
 
    static void bfs() {
        int size = 2;
        int eat = 0;
        while (true) {
            boolean chk = false;
            ArrayList<int[]> eatlist = new ArrayList<>();
            for (int t = 1;; t++) {
                int qsize = dq.size();
                while (qsize-- > 0) {
                    int x = dq.peek()[0];
                    int y = dq.poll()[1];
 
                    for (int i = 0; i < 4; i++) {
                        int nx = x + direct[i][0];
                        int ny = y + direct[i][1];
 
                        if (nx < 0 || ny < 0 || nx >= N || ny >= N)
                            continue;
                        if (visit[nx][ny])
                            continue;
                        if (list[nx][ny] > size)
                            continue;
 
                        if (list[nx][ny] != 0 && list[nx][ny] < size) {
                            eatlist.add(new int[] { nx, ny });
                        }
                        dq.add(new int[] { nx, ny });
                        visit[nx][ny] = true;
                    }
                }
 
                if (!eatlist.isEmpty()) {
                    ans += t;
                    break;
                }
                if (dq.isEmpty()) {
                    chk = true;
                    break;
                }
            }
 
            if (chk)
                break;
 
            Collections.sort(eatlist, new Comparator<int[]>() {
                @Override
                public int compare(int[] a, int[] b) {
                    if (a[0] == b[0])
                        return a[1] - b[1];
                    else
                        return a[0] - b[0];
                }
            });
 
            int x = eatlist.get(0)[0];
            int y = eatlist.get(0)[1];
            list[x][y] = 0;
            eat++;
            if (eat == size) {
                eat = 0;
                size++;
            }
 
            dq.clear();
            eatlist.clear();
            for (int i = 0; i < N; i++)
                Arrays.fill(visit[i], false);
            dq.add(new int[] { x, y });
            visit[x][y] = true;
        }
        System.out.println(ans);
    }
 
    static void input() throws Exception {
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < N; j++) {
                list[i][j] = Integer.parseInt(st.nextToken());
                if (list[i][j] == 9) {
                    list[i][j] = 0;
                    dq.add(new int[] { i, j });
                    visit[i][j] = true;
                }
            }
        }
    }
 
    public static void main(String[] args) throws Exception {
        input();
        bfs();
    }
}