2 분 소요

문제

문제 바로가기

입력

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

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

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

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

출력

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

접근방법

  1. 아기 상어의 초기 위치를 찾는다.
  2. 아기 상어가 먹을 수 있는 물고기 중 bfs를 이용하여 가장 가까운 물고기를 찾는다.
  3. 최단 경로가 여러 개인 경우에 가장 위쪽에 있는 물고기, 그러한 물고기가 여러 마리인 경우 가장 왼쪽에 있는 물고기를 먹는다.
  4. 먹은 물고기의 위치로 이동하고 빈 칸으로 만들어준다.
  5. 먹은 물고기의 수가 아기 상어의 크기와 같아지면 크기를 1 증가시킨다.
  6. 더 이상 먹을 수 있는 물고기가 없을 때까지 반복하고 총 걸린시간을 출력한다.

풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

class Coo {
    int cx, cy, time;
    Coo(int x, int y, int time) {
        this.cx = x;
        this.cy = y;
        this.time = time;
    }
}
public class Main {
    static int N;
    static int[][] map;
    static int x, y;
    static int[] dx = {-1, 0, 1, 0};
    static int[] dy = {0, -1, 0, 1};
    static int size = 2;
    static int cnt = 0;
    static int second = 0;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        map = new int[N][N];

        for(int i = 0; i < N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for(int j = 0; j < N; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
                if(map[i][j] == 9) {
                    x = i;
                    y = j;
                }
            }
        }

        while(true) {
            map[x][y] = 0;
            ArrayList<Coo> tmp = bfs(x, y);
            if(tmp.isEmpty()) {
                break;
            }
            int mx = Integer.MAX_VALUE;
            int my = Integer.MAX_VALUE;
            int distance = Integer.MAX_VALUE;
            int idx = 0;
            for(int i = 0; i < tmp.size(); i++) {
                if(distance >= tmp.get(i).time) {
                    distance = tmp.get(i).time;
                    if (mx > tmp.get(i).cx) {
                        mx = tmp.get(i).cx;
                        my = tmp.get(i).cy;
                        idx = i;
                    } else if (mx == tmp.get(i).cx) {
                        if (my > tmp.get(i).cy) {
                            my = tmp.get(i).cy;
                            idx = i;
                        }
                    }
                }
            }

            x = tmp.get(idx).cx;
            y = tmp.get(idx).cy;
            cnt++;
            second += tmp.get(idx).time;
            if (cnt == size) {
                size++;
                cnt = 0;
            }

        }

        System.out.println(second);
    }

    public static ArrayList<Coo> bfs(int a, int b) {
        int[][] check = new int[N][N];
        ArrayList<Coo> arr = new ArrayList<>();
        Queue<int[]> q = new LinkedList<>();
        q.offer(new int[] {a, b});
        check[a][b]++;
        while(!q.isEmpty()) {
            int[] temp = q.poll();
            int tx = temp[0];
            int ty = temp[1];
            for(int i = 0; i < 4; i++) {
                int nx = tx + dx[i];
                int ny = ty + dy[i];
                if(nx >= 0 && ny >= 0 && nx < N && ny < N) {
                    if(check[nx][ny] == 0) {
                        if (map[nx][ny] < size && map[nx][ny] > 0) {
                            arr.add(new Coo(nx, ny, check[tx][ty]));
                            check[nx][ny] = check[tx][ty];
                        }
                        else if(map[nx][ny] == 0 || map[nx][ny] == size){
                            q.offer(new int[]{nx, ny});
                            check[nx][ny] = check[tx][ty] + 1;
                        }
                    }
                }
            }
        }
        return arr;
    }
}

댓글남기기

참고