공부흔적

문제 링크

풀이 ) BFS

  현재 아기상어 위치를 시작으로 BFS로 먹이 후보를 찾고

  후보 중 조건에 만족하는 먹이로 이동하기를 이동할 수 없을 때까지 반복한다.

코드 )

import java.io.*;
import java.util.*;

class Main {

    static int n;
    static int[][] board;
    static boolean[][] visited;
    static Fish shark;
    static Fish next;
    static Queue<Fish> q;

    static int answer;

    static int[] dx = {-1, 0, 0, 1};
    static int[] dy = {0, -1, 1, 0};

    public static void main(String[] args) throws IOException {
        input();	// 입력
        solve();	// 풀이
    }

    static void solve() {

        while(true) {
            int distance = init();	// 현재 상어 위치부터 다음 먹이까지의 거리 (초기화)

            while(!q.isEmpty() && next == null) {	// 다음 물고기가 없을때까지
                int size = q.size();
                distance++;
                while (size-- > 0) {
                    Fish cur = q.poll();
                    /*
                     * 다음 물고기의 크기가 더 작은 지 확인하고
                     * 더 작으면 먹을 수 있는 다른 물고기와 위치를 비교하여 갱신
                     */
                    promise(cur.x, cur.y);

                    for (int dir = 0; dir < 4; ++dir) {
                    	// 다음 위치로 이동할 수 있으면 추가
                        findRoute(cur.x+dx[dir], cur.y+dy[dir]);
                    }
                }
            }

            if(next != null) {
            	// 이동 가능한 경우
                move(distance);
            } else {
            	// 이동 불가능한 경우
                System.out.println(answer);
                break;
            }
        }
    }

    static void move(int distance) {
        answer += distance;
        // 물고기를 먹고
        board[next.x][next.y] = 0;
        shark = next;
        // 크기가 증가할 수 있으면 증가
        shark.grow();
    }

    static void findRoute(int x, int y) {
        if (!isIn(x, y) || visited[x][y] || board[x][y] > shark.size){
            return;
        }

        visited[x][y] = true;
        q.offer(new Fish(x, y, board[x][y], -1));
    }

    static void promise(int x, int y) {
        if (board[x][y] > 0 && board[x][y] < shark.size) {
            Fish candidate = new Fish(x, y, shark.size, shark.feed+1);
            if(next == null ||
                    candidate.x < next.x ||
                    (candidate.x == next.x && candidate.y < next.y)) {
                next = candidate;
            }
        }
    }

    static int init() {
        visited = new boolean[n][n];
        q = new LinkedList<>();
        q.offer(shark);
        visited[shark.x][shark.y] = true;
        next = null;
        return -1;
    }

    static boolean isIn(int nx, int ny) {
        return nx>=0&&nx<n&&ny>=0&&ny<n;
    }

    static void input() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        board = new int[n][n];
        for(int i = 0; i < n; ++i) {
            StringTokenizer st = new StringTokenizer(br.readLine(), " ");
            for(int j = 0; j < n; ++j) {
                board[i][j] = Integer.parseInt(st.nextToken());
                if(board[i][j] == 9) {
                    shark = new Fish(i, j, 2, 0);
                    board[i][j] = 0;
                }
            }
        }
    }

    static class Fish {
        int x, y;
        int size;
        int feed;

        public Fish(int x, int y, int size, int feed) {
            this.x = x;
            this.y = y;
            this.size = size;
            this.feed = feed;
        }

        void grow() {
            if(feed == size) {
                size++;
                feed = 0;
            }
        }
    }
}

주의 )

  단순히 상, 좌, 우, 하 순으로 검사하게되면 4번 예시 케이스에서 답인 60이 아닌 56이 출력된다.

문제 링크

풀이 )

  하나의 칸에 여러 나무가 있을 때 나이가 적은 나무부터 양분을 공급한다는 내용을 보고 우선순위큐를 사용했다.

  feed 배열에는 양분을 저장했고, a 배열에는 겨울마다 늘어나는 양분을 저장했다.

  나무의 좌표와 나이를 저장하는 우선순위큐를 만들어서 나이가 낮은 순으로 poll 되도록 구현했다.

  처음에는 우선순위큐 하나만 사용해서 구현하려고했기 때문에 큐의 크기를 먼저 구한 후 큐의 크기만큼만 반복문을 돌렸지만, 이런 경우 중간에 나이가 낮은 나무가 들어오는 경우 의도와 다르게 나오는 경우가 있었기 때문에 다른 우선순위 큐를 선언해서 사용했다.

  나머지는 문제에서 요구하는 순서대로 구현했다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
    static int[] dx = {0, 1, 1, 1, 0, -1, -1, -1};
    static int[] dy = {1, 1, 0, -1, -1, -1, 0, 1};

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());
        int[][] feed = new int[n+1][n+1];
        int[][] a = new int[n+1][n+1];

        PriorityQueue<Info> treeQ = new PriorityQueue<>((o1, o2)->{
            return o1.age-o2.age;
        });
        Queue<Info> dieQ = new LinkedList<>();

        for(int i = 1; i <= n; ++i){
            st = new StringTokenizer(br.readLine(), " ");
            for(int j = 1; j <= n; ++j){
                feed[i][j] = 5;
                a[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        for(int i = 0; i < m; ++i){
            st = new StringTokenizer(br.readLine(), " ");
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());
            int age = Integer.parseInt(st.nextToken());
            treeQ.offer(new Info(x, y, age));
        }
        // 입력

        while(k-- > 0) {
            PriorityQueue<Info> tmp = new PriorityQueue<>((o1, o2)->{
                return o1.age-o2.age;
            });
            int size = treeQ.size();
            while (size-- > 0) {
                Info tree = treeQ.poll();
                int x = tree.x, y = tree.y, age = tree.age;
                if (feed[x][y] >= age) {
                    feed[x][y] -= age;
                    age++;
                    tmp.offer(new Info(x, y, age));
                } else
                    dieQ.offer(new Info(x, y, age));
            }
            treeQ = tmp;
            // 봄

            while (!dieQ.isEmpty()) {
                Info die = dieQ.poll();
                feed[die.x][die.y] += die.age / 2;
            }
            // 여름

            PriorityQueue<Info> tmp2 = new PriorityQueue<>((o1, o2)->{
                return o1.age-o2.age;
            });
            size = treeQ.size();
            while (size-- > 0) {
                Info tree = treeQ.poll();
                tmp2.offer(tree);
                if (tree.age % 5 == 0) {
                    int x = tree.x, y = tree.y;
                    for (int dir = 0; dir < 8; ++dir) {
                        int nx = x + dx[dir], ny = y + dy[dir];
                        if (0 < nx && nx <= n && 0 < ny && ny <= n)
                            tmp2.offer(new Info(nx, ny, 1));
                    }
                }
            }
            treeQ = tmp2;
            // 가을

            for(int i = 1; i <= n; ++i){
                for(int j = 1; j <= n; ++j)
                    feed[i][j] += a[i][j];
            }
            // 겨울
        }
        System.out.println(treeQ.size());
    }

    static class Info{
        int x, y, age;

        public Info(int x, int y, int age) {
            this.x = x;
            this.y = y;
            this.age = age;
        }
    }
}