[BOJ] 16236. 아기상어 - Simultaion

[BOJ] 16236. 아기상어 - Simultaion

제출일 : 2019-10-15

문제 풀이 시간 : 1H

난이도 : ★★★

Problem

link : https://www.acmicpc.net/problem/16236

Input

첫째 줄에 공간의 크기 N(2 ≤ N ≤ 20)이 주어진다.

둘째 줄부터 N개의 줄에 공간의 상태가 주어진다. 공간의 상태는 0, 1, 2, 3, 4, 5, 6, 9로 이루어져 있고, 아래와 같은 의미를 가진다.

• 0: 빈 칸
• 1, 2, 3, 4, 5, 6: 칸에 있는 물고기의 크기
• 9: 아기 상어의 위치

아기 상어는 공간에 한 마리 있다.

Output

첫째 줄에 아기 상어가 엄마 상어에게 도움을 요청하지 않고 물고기를 잡아먹을 수 있는 시간을 출력한다.

Example

input

6
5 4 3 2 3 4
4 3 2 3 4 5
3 2 9 5 6 6
2 1 2 3 4 5
3 2 1 6 5 4
6 6 6 6 6 6

output

60

Solution & Inpression

시뮬레이션 문제

문제에서 시키는데로 차근차근 풀게되면 어려움이 없는 문제

BFS를 이용하여 먹을수 있는 물고기를 ArrayList에 저장하고, 어떤 물고기를 먼저 먹을지 문제에 주어졌고 ArrayList의 정렬조건을 문제에서 주어진대로 주고 가장 첫번째 인덱스의 물고기를 잡아먹었다.

Code

언어 : JAVA

메모리 : 21,144 kb

실행시간 : 192 ms

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {
    static int N, time;
    static int[][] map;
    static int[] dr = { 1, -1, 0, 0 };
    static int[] dc = { 0, 0, 1, -1 };
    static Shark s;

    static class Shark {
        int size, r, c, count;

        @Override
        public String toString() {
            return "Shark [size=" + size + ", r=" + r + ", c=" + c + ", count=" + count + "]";
        }

    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        // 0: 빈 칸
        // 1, 2, 3, 4, 5, 6: 칸에 있는 물고기의 크기
        // 9: 아기 상어의 위치
        map = new int[N][N];
        s = new Shark();
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                int tmp = sc.nextInt();
                map[i][j] = tmp;
                if (tmp == 9) {
                    s.r = i;
                    s.c = j;
                    s.size = 2;
                    s.count = 0;
                }
            }
        }
        time = 0;
        while (move(s)) {
        }
        System.out.println(time);

    }

    private static boolean move(Shark s) {

        boolean[][] visit = new boolean[N][N];
        Queue<int[]> q = new LinkedList<>();
        ArrayList<int[]> list = new ArrayList<>();
        q.offer(new int[] { s.r, s.c, 0 });
        visit[s.r][s.c] = true;

        while (!q.isEmpty()) {
            int[] cur = q.poll();
            for (int k = 0; k < 4; k++) {
                int r = cur[0] + dr[k];
                int c = cur[1] + dc[k];

                if (range(r, c) && !visit[r][c]) {
                    visit[r][c] = true;
                    if (map[r][c] > s.size)// 지나가지도 먹지도 못함
                        continue;
                    else if (map[r][c] == s.size || map[r][c] == 0) // 지나갈순 있지만 먹진 못함.
                        q.offer(new int[] { r, c, cur[2] + 1 });
                    else {
                        list.add(new int[] { r, c, cur[2] + 1 });
                    }
                }
            }
        } // end of while

        if (list.isEmpty())
            return false;
        else {
            Collections.sort(list, new Comparator<int[]>() {
                public int compare(int[] o1, int[] o2) {
                    int r = o1[2] - o2[2]; // 거리순으로
                    if (r == 0) {// 위쪽 우선순위
                        int r2 = o1[0] - o2[0];
                        if (r2 == 0) {// 왼쪽 우선순위
                            return o1[1] - o2[1];
                        } else
                            return r2;
                    } else
                        return r;
                }
            });

            eat(list.get(0));
            return true;
        }

    }

    private static void eat(int[] fish) {
        time += fish[2];
        map[s.r][s.c] = 0;
        s.r = fish[0];
        s.c = fish[1];
        s.count++;
        if (s.count == s.size) {
            s.size++;
            s.count = 0;
        }
        map[fish[0]][fish[1]] = 9;
    }

    private static boolean range(int r, int c) {
        if (0 <= r && r < N && 0 <= c && c < N)
            return true;
        return false;
    }
}