SW 역량 테스트 기출 문제(아기상어)

[아기상어 _ 16236]

 

 

* 조건

1. 아기상어는 1마리, 물고기는 m마리
2. 한 칸에는 물고기가 최대 1마리
3. 아기상어
   • 가장 처음 아기상어의 크기 = 2
   • 1초에 상하좌우 한 칸씩 이동 가능
   • 상어 >= 물고기 크기여야만 먹거나 이동 가능
   • 물고기를 먹은 횟수 == 상어의 현재 크기이면 상어의 사이즈++
4. 먹을 수 있는 물고기
   • 1마리 -> 해당 물고기를 먹고 이동
   • 2마리 이상 -> 거리순으로 판단 -> 거리가 같다면 더 위에 있는 순으로 판단 -> 같은 레벨이라면 더 왼쪽에 있는 순으로 잡아먹을 물고기의 우선순위를 측정
   • 물고기를 먹게되면 해당 칸의 값 = 0

* 알고리즘

- 매 초마다 상하좌우로 주변을 탐색하며 물고기의 유무 확인: BFS

 

* 로직(Logic)

- 1초 사이클
: 현재 상어의 위치를 기준으로 상하좌우 인접한 곳 탐색 -> 한 칸씩 탐색을 하면서 해당 칸에 먹을 수 있는 물고기가 존재한다면 -> (조건-4)를 고려하며 가장 우선순위의 물고기 정보를 저장 -> 우선순위가 가장 높은 물고기의 정보만 큐에 넣고 나머지는 초기화 -> 상어의 위치 이동

 

- 물고기를 먹게되면 -> 해당칸의 값 = 0 && eatCount++

- eatCount == 상어의 크기 -> 상어의 크기++

 

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

class Position_16236_ {
    public int y,x;
    public int step;
    public int size;

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

public class Problem_16236_ {

    static int N;
    static int[][] map;

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

    static boolean[][] checked;

    static int eatCount = 0;
    static Queue<Position_16236_> queue;
    static Position_16236_ shark;

    static int answer = 0;

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

        N = Integer.parseInt(br.readLine());
        map = new int[N][N];
        for(int i=0; i<N; ++i){
            String input = br.readLine();
            st = new StringTokenizer(input, " ");
            for(int j=0; j<N; ++j){
                map[i][j] = Integer.parseInt(st.nextToken());
                if(map[i][j] == 9){
                    shark = new Position_16236_(i, j);
                    shark.step = 0;
                    shark.size = 2;
                    map[i][j] = 0;
                }
            }
        }

        searchFish();
        System.out.println(answer);
    }

    private static void searchFish() {
        queue = new LinkedList<>();
        checked = new boolean[N][N];

        queue.offer(shark);
        checked[shark.y][shark.x] = true;

        while (!queue.isEmpty()){
             int queueSize = queue.size();
             int tmp_step = Integer.MAX_VALUE;
             int tmp_y = N+1;
             int tmp_x = N+1;
             boolean findFish = false;

             for(int s=0; s<queueSize; ++s){
                 Position_16236_ q = queue.poll();

                 //1초동안 상하좌우 탐색
                 for(int i=0; i<4; ++i){
                     int moveY = q.y + dy[i];
                     int moveX = q.x + dx[i];

                     //탐색을 한칸씩 하면서 -> 해당 칸에 물고기가 존재한다면 -> step을 비교해서 넣어주고, 좌표를 넣어줌
                     //       -> 상하좌우를 탐색하면서 조건에 충족하는 최종 step과 좌표가 생기고 -> 이를 큐에 넣어줌
                     //만약 물고기가 존재하지 않는다면('0') 그냥 큐에 삽입
                     if(isRanged(moveY, moveX) && !checked[moveY][moveX] && shark.size >= map[moveY][moveX]){
                         int moveStep = q.step + 1;

                         //먹을 수 있는 물고기가 존재한다면
                         if(map[moveY][moveX] > 0 && map[moveY][moveX] < shark.size){
                             if(tmp_step > moveStep){
                                 tmp_step = moveStep;
                                 tmp_y = moveY;
                                 tmp_x = moveX;
                             }
                             //거리가 같다면
                             else if(tmp_step == moveStep){
                                 //더 위에 있는 물고기
                                 if(tmp_y > moveY){
                                     tmp_y = moveY;
                                     tmp_x = moveX;
                                 }

                                 //높이가 같다면
                                 else if(tmp_y == moveY){
                                     //더 왼쪽에 있는 물고기
                                     if(tmp_x > moveX){
                                         tmp_y = moveY;
                                         tmp_x = moveX;
                                     }
                                 }
                             }
                             findFish = true;
                         }

                         Position_16236_ tmp = new Position_16236_(moveY, moveX);
                         tmp.step = moveStep;
                         tmp.size = map[moveY][moveX];

                         queue.offer(tmp);
                         checked[moveY][moveX] = true;
                     }
                 }
             }

             if(findFish){
                 while (!queue.isEmpty()) queue.poll();
                 checked = new boolean[N][N];

                 //우선순위로 선정된 물고기를 먹고
                 map[tmp_y][tmp_x] = 0;
                 eatCount++;

                 //먹는데 걸린 초 누적
                 answer += tmp_step;

                 //상어 이동 + 큐에 삽입
                 Position_16236_ movedShark = new Position_16236_(tmp_y, tmp_x);
                 movedShark.step = 0;
                 movedShark.size = map[tmp_y][tmp_x];
                 queue.offer(movedShark);
                 checked[tmp_y][tmp_x] = true;

                 //상어의 전역객체도 수정
                 shark.y = movedShark.y;
                 shark.x = movedShark.x;

                 //먹은 물고기의 개수가 상어의 크기와 같으면 사이즈++
                 if(eatCount == shark.size) {
                     shark.size++;
                     eatCount = 0;
                 }
             }
        }
    }

    private static boolean isRanged(int y, int x) {
        if(y>=0 && y<N && x>=0 && x<N) return true;
        return false;
    }
}

 

위와 같이 해결하기 전에 우선순위 큐를 생성하고 comparator 메소드에 (조건-4)를 고려하여 정렬을 시도하는 방법을 생각해보고 적용했는데 약간씩 오류가 생겼었다. 다시 한번 시도해봐야겠다.

로직을 짜는데 있어서 한 사이클동안 어디까지를 진행하느냐에 따라 제약조건, 실행 순서가 달라진다는 것을 다시 한번 느꼈고, 항상 사이클의 범위와 어디서부터 시작하고 끝낼지를 잘 짜내는 연습을 해야겠다는 생각을 했다.