[BOJ] 삼성 sw 역량 테스트 기출 :: 16236번 아기 상어 (java)

BOJ 16236번 아기 상어 문제 자바(java) 풀이

• 랭크 : 골드5
• 백준 16236번 아기 상어

문제 정리

1. NxN 크기의 공간
2. M마리의 물고기
3. 아기 상어 1마리
4. 한 칸에는 물고기가 최대 1마리 존재(없거나 1마리)
5. 초기 아기상어의 크기는 2
6. 1초에 상하좌우 한 칸씩 이동
7. 자신의 크기보다 큰 물고기가 있는 칸 제외 모든 칸 지나갈 수 있음
8. 자기보다 작은 물고기 먹을 수 있음, 크기 같으면 지나만 갈 수 있음
9. 이동 결정 알고리즘

• 더 이상 먹을 수 있는 물고기가 없으면 엄마에게 도움을 청함
• 먹을 수 있는 물고기가 1마리면 그 물고기를 먹으러 감
• 먹을 수 있는 물고기가 1마리 보다 많다면, 거리가 가장 가까운 물고기를 먹으러 감
• 거리: 아기 상어가 있는 칸에서 물고기가 있는 칸으로 이동할 때, 지나야하는 칸의 개수의 최솟값
• 거리가 가까운 물고기가 많다면, 가장 위, 가장 왼쪽에 있는 물고기를 먹음

10. 이동과 동시에 물고기를 먹음(먹을 수 있다면)
11. 자신의 크기와 같은 수의 물고기를 먹을 때마다 크기 1 증가
12. 아기 상어가 몇 초동안 엄마에게 도움을 청하지 않고 물고기를 먹을 수 있는가????
    
    
    

문제 풀이(우선순위 큐)

처음에는 우선순위 큐를 이용하여 구하였다.
먹을 물고기를 결정할때 이용하면 되겠다고 생각했기 때문이다.
답은 나왔지만 실행시간이 오래걸렸다.

1. map을 입력받고 상어의 위치는 따로 저장한다.(상어의 위치 0으로)
2. NxN의 맵을 순회하며 먹을 수 있는 경우 distance를 구한다.
3. 구한 distance를 우선순위 큐에 넣는다(우선순위큐는 dist 기준 오름차순, 같을시 x기준 오름차순, x도 같을시 y기준 오름차순)
4. 먹을 물고기의 위치를 우선순위 큐에서 꺼낸다.
5. time을 거리 만큼 더한다.
6. 상어의 위치를 먹은 물고기의 위치로 변환한다.
7. 상어가 먹은 물고기의 개수를 증가시키고 맵에서 물고기의 자리를 0으로 바꾼다.
8. 상어가 먹은 먹이의 개수가 크기가 되는지 확인 후 크기를 update 한다.
9. 먹을 것이 없을 때까지 반복한다.
10. 먹을 것이 있는지 없는지 판단은 bfs를 통해 확인한다. 거리도 bfs를 통해 구한다.
    
    
    

문제 풀이2(거리 배열)

그래서 빠른 시간안에 푼 풀이는 어떻게 풀었는지 확인하였다.
전에 써먹었던 방식인데 왜 기억이 안났는지...ㅠㅠㅠ
상어의 위치에서 bfs 방식으로 거리를 update하며 먹을 수 있는 가장 가까운 물고기의 위치를 찾는다.

1. 거리를 담은 배열과 최소 위치를 초기화 한다.
2. bfs를 통해 가장 가까운 물고기의 위치를 찾는다.
3. 4방향을 탐색하면서 이동가능하면서 방문하지 않은 곳인지 확인한다. 이동가능하면 1칸 이동하고 check를 갱신한다.
4. 먹을 수 있는지 확인한다.
5. 먹을 수 있다면 거리가 최소인지 확인한다.
6. 거리가 같다면 x를 비교하고 x도 같다면 y를 비교한다.
7. 계속 이동해 나간다.
8. 나머지는 1번 풀이와 같다.
   
   
   

풀이 1번은 992ms 걸렸고

풀이 2번은 164ms가 걸렸습니다.

풀이 1번은 아래 깃헙을 참고하시면 되고 코드 2번만 아래에 올렸습니다.

https://github.com/wlgh325/BOJ_answer/blob/master/%EC%82%BC%EC%84%B1%20SW%20%EC%97%AD%EB%9F%89%20%ED%85%8C%EC%8A%A4%ED%8A%B8/16236(%EC%95%84%EA%B8%B0%20%EC%83%81%EC%96%B4)/Main.java

wlgh325/BOJ_answer

백준 16236번 아기 상어 자바 풀이2

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
 
class Pos{
    int x;
    int y;
    
    Pos(int x, int y){
        this.x = x;
        this.y = y;
    }
}
 
class Shark{
    Pos pos;
    int feed;
    int size;
 
    Shark(Pos pos, int feed){
        this.pos = pos;
        this.feed = feed;
        this.size = 2;
    }
}
 
class Main {
 
    static int N, minDist, minX, minY;
    static int[][] map, check;
    static Shark shark;
    // 상, 하, 좌, 우
    static int[] xdir = {-1,1,0,0};
    static int[] ydir = {0,0,-1,1};
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
        int time = 0;
        N = Integer.parseInt(br.readLine());
 
        // initialize
        map = new int[N][N];
        check = new int[N][N];
        
        for(int i=0; i<N; i++){
            String[] temp = br.readLine().split(" ");
            for(int j=0; j<N; j++){
                int num = Integer.parseInt(temp[j]);
                
                // 아기 상어
                if(num == 9)    shark = new Shark(new Pos(i, j), 0);
                else if(num != 0)    map[i][j] = num;
            }
        }
 
        while(true){
            init();
            if(!isPossibleFeed()) break;
 
            findCloseFish();
 
            // 이동
            time += minDist;
            shark.pos.x = minX;
            shark.pos.y = minY;
 
            // 먹고 제거
            shark.feed++;
            map[minX][minY] = 0;
            if(shark.feed == shark.size){
                shark.feed = 0;
                shark.size++;
            }
        }
 
        System.out.println(time);
    }
 
    public static void init() {
        minDist = Integer.MAX_VALUE;
        minX = Integer.MAX_VALUE;
        minY = Integer.MAX_VALUE;
        
        for(int i=0; i<N; i++) {
            for(int j=0; j<N; j++) {
                check[i][j] = -1;
            }
        }
    }
 
    public static void findCloseFish(){
        Queue<Pos> q = new LinkedList<>();
        int size = shark.size;
        check[shark.pos.x][shark.pos.y] = 0;
 
        q.offer(shark.pos);
        
        while(!q.isEmpty()){
            Pos p = q.poll();
            int x = p.x;
            int y = p.y;
 
            for(int i=0; i<4; i++){
                int dx = x + xdir[i];
                int dy = y + ydir[i];
                
                // 이동 가능한 곳이고, 방문하지 않은 곳인 경우 이동
                if(isValidPosition(dx, dy) && map[dx][dy] <= size && check[dx][dy] == -1){
                    check[dx][dy] = check[x][y] + 1;
 
                    // 먹을 수 있는지 확인
                    if(map[dx][dy] != 0 && map[dx][dy] < size) {
                        // 그 중에서 가장 가까운건지 확인
                        if(minDist > check[dx][dy]) {
                            minX = dx;
                            minY = dy;
                            minDist = check[dx][dy];
                        }
                        else if(minDist == check[dx][dy]) {
                            if(minX == dx) {
                                // 같은 높이면 더 왼쪽
                                if(minY > dy) {
                                    minX = dx;
                                    minY = dy;
                                }
                            }
                            else if(minX > dx) {
                                // 더 위에 있는 거
                                minX = dx;
                                minY = dy;
                            }
                        }
                    }
                    q.offer(new Pos(dx, dy));
                }
            }
        }
    }
 
    public static boolean isPossibleFeed(){
        Queue<Pos> q = new LinkedList<>();
        boolean[][] visited = new boolean[N][N];
        
        visited[shark.pos.x][shark.pos.y] = true;
        q.offer(new Pos(shark.pos.x, shark.pos.y));
        while(!q.isEmpty()){
            Pos p = q.poll();
            int x = p.x;
            int y = p.y;
 
            for(int i=0; i<4; i++){
                int dx = x + xdir[i];
                int dy = y + ydir[i];
                if(isValidPosition(dx, dy) && !visited[dx][dy]){
                    if(map[dx][dy] == shark.size || map[dx][dy] == 0){
                        q.offer(new Pos(dx, dy));
                        visited[dx][dy] = true;
                    }
                    else if(map[dx][dy] < shark.size){
                        return true;
                    }
                }
            }
        }
        return false;
    }
 
    public static boolean isValidPosition(int x, int y){
        if(x < 0 || x >= N || y < 0 || y >= N) return false;
        return true;
    }
}