[BOJ] 16236 아기상어 - Java

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

16236번: 아기 상어

[풀이]

문제에 조건이 많고, 어떻게 풀이해야 할지 감이 잘 안와서 20분 넘게 펜으로 고민해본 문제이다.

문제를 보고 상어가 이동하면서 체크해야 할 것은 "가장 가까운 거리에 위치하는 물고기 파악" 이었다.

근데 이를 어떻게 판단할 것인가? 문제에서 상어는 못 가는 곳도 있어서 운이 나쁘다면 상어는 삥 돌아가야 하는 경우가 존재할 것이다.

최단거리는 그럼 어떻게 찾을 수 있을까?

 

1. 처음에는 dfs로 생각했다. (아무생각없이 dfs를 택했다.) 근데 코드를 열심히 짜고나니, 방문배열을 이용하는 로직이 좀 애매했다.

A -> B -> C -> D 를 가는 길이 있고 A -> E -> D 를 가는 길이 있다고 하자. ABCD를 먼저 방문한 후 AED를 방문한다면 D는 최단거리를 보장받지 못한다.

 

2. 그러다가 생각한 것이 지금 얘는 한 점에서 다른 모든 점까지의 최단 거리를 구해야 한다는 것이었다. 

갔던 길을 다시 돌아오는 경로는 존재하지 않고, 쭉쭉 뻗어나가기만 한다.

=> 그렇다면! BFS를 사용할 수 있을 것이라는 생각이 들었다.

 BFS는 visit 배열을 하나 두고 한 점에서 쭉쭉 뻗어나간다. 큐에 저장하는 자료형에 count변수를 둔다면 얘가 몇 번째 뻗어나간 애인지도 제어할 수 있다.

 

3. 먹을 수 있는 물고기는 거리가 가장 가까운 애, row가 작은 애, col이 작은 애 순으로 정해진다. Fish라는 자료형을 두고 PriorityQueue를 이용했다.

public static class Fish implements Comparable<Fish>{
    int row;
    int col;
    int count;

    public Fish(int row, int col, int count) {
        this.row = row;
        this.col = col;
        this.count = count;
    }

    //거리가 가까운 순, 거리가 가까운 물고기가 많다면 가장 위에 있는 물고기, 그러한 물고기가 여러마리라면 가장 왼쪽에 있는 물고기
    @Override
    public int compareTo(Fish o) {
        int cmp = Integer.compare(count,o.count);
        if(cmp==0){
            cmp = Integer.compare(row,o.row);
            if(cmp==0){
                cmp = Integer.compare(col,o.col);
            }
        }
        return cmp;
    }
}

 

4. (독해력이 딸렸던 부분) 아기 상어는 자신의 크기와 같은 수의 물고기를 먹을 때 마다 크기가 1 증가한다. 예를 들어, 크기가 2인 아기 상어는 물고기를 2마리 먹으면 크기가 3이 된다.

-> 아뿔싸 처음 문제 읽을 때 대충 읽고 당연히 물고기 먹으면 그 물고기 사이즈만큼 흡수하는 걸로 이해했다. (그래서 예제 3 답이 계속 12가 나옴) 손으로 해도 12가 나오길래 아 딴거 잘못했나보다하고 처음부터 조건 다 살펴봤다.

-> 이 조건 발견. 근데 또또 잘못 이해함 (물고기 하나 먹을 때마다 크기가 1증가한다로..) 또 답이 12가 계속 나오더라

-> 세번째 다시 읽었을 때 깨달았다.

=> 상어는 '자기 크기랑 같은 수'의 물고기를 먹을 때마다 1씩 증가한다.

 

상어 크기가 2일 때 물고기를 2번 먹으면 -> 3이 된다. 

상어 크기가 3일 때 물고기를 3번 먹으면 -> 4가 된다.

=> 먹은 물고기의 개수 % 상어 크기 == 0 이면 크기를 1씩 증가시켜주자.

(단, 먹은 물고기의 개수는 상어의 크기가 증가할 때마다 0으로 초기화해줌)

ex) 상어크기 2 , 물고기 1번 -> 상어크기 2, 물고기 2번 (2%2==0) => 3으로 UPGRADE , 물고기 0번으로 설정
상어크기 3, 물고기 1번 -> 상어크기 3, 물고기 2번 -> 상어크기 3, 물고기 3번 (3%3==0) => 4로 UPGRADE, 물고기 0번으로 설정 ..

eatFishNum++;
//아기상어는 자신의 크기와 같은 수의 물고기를 먹을 때마다 크기가 1 증가한다.
int Size = shark.size;
if(eatFishNum % shark.size==0){
    Size = shark.size+1;
    eatFishNum = 0;
}

5. 또 기타 주의해야할 조건은 더이상 먹을 수 있는 물고기가 없으면 엄마찬스 써야 한다는 것 정도?

//물고기 잡을 수 있는지 확인
if(queue.isEmpty()){
    break; //더이상 먹을 수 있는 물고기가 없다면 엄마찬스
}

 

[코드]

import java.io.*;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.StringTokenizer;

public class Boj16236_아기상어 {
    static StringTokenizer st;
    static int N;
    static int[][] Map;
    static Shark shark;
    static int answer;
    static int[] dRow = {-1,1,0,0};
    static int[] dCol = {0,0,-1,1};
    static boolean[][] visit;
    static int fishNum = 0;
    static int eatFishNum = 0;

    public static void main(String[] args) throws Exception{
        System.setIn(new FileInputStream("src/main/java/input.txt"));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        N = Integer.parseInt(br.readLine());
        Map = new int[N+1][N+1];

        for(int i=1;i<N+1;i++){
            st = new StringTokenizer(br.readLine());
            for(int j=1;j<N+1;j++){
                Map[i][j] = Integer.parseInt(st.nextToken());
                if(1<=Map[i][j] && Map[i][j]<=6){
                    fishNum++; //총 물고기 개수
                }
                if(Map[i][j] == 9){
                    shark = new Shark(i,j,2); //상어 정보 저장
                    Map[i][j] = 0; //상어 정보는 저장했으므로 9는 이제 빈칸으로 취급해야 함
                }
            }
        }


        while(true){
            if(fishNum<=0){ //물고기 다 먹으면 끝
                break;
            }

            //상어 이동시킬때마다 초기화
            PriorityQueue<Fish> queue = new PriorityQueue<>(); //상어가 먹을 수 있는 물고기 후보들 -> 우선순위큐 사용
            visit = new boolean[N+1][N+1]; //상어가 방문한 좌표 관리
            Queue<Shark> move = new LinkedList<>(); // 상어가 이동하는 좌표(bfs돌리면서 여기다 담을거임)
            move.add(shark); //상어가 처음 있는 곳
            visit[shark.row][shark.col] = true; //상어가 처음 있는 곳 방문처리

            //bfs 시작
            while(!move.isEmpty()){
                Shark now = move.poll();
                for(int i=0;i<4;i++) {
                    int newRow = now.row + dRow[i];
                    int newCol = now.col + dCol[i];

                    if (0 < newRow && newRow <= N && 0 < newCol && newCol <= N) { //범위 확인
                        if (!visit[newRow][newCol]) { //방문할 수 있다면
                            visit[newRow][newCol] = true; //방문처리
                            if (Map[newRow][newCol] <= shark.size) { //상어가 갈 수 있냐? //0,같거나 작은 곳
                                if (Map[newRow][newCol] < shark.size && Map[newRow][newCol] != 0) { //먹을수 있는 물고기냐? //작은 곳
                                    queue.add(new Fish(newRow, newCol, now.count+1)); //물고기 후보에 추가
                                }
                                move.add(new Shark(newRow, newCol, now.size, now.count + 1)); //0,같거나 작은 곳에서 모두 가야하므로 move에 좌표 추가
                            }
                        }
                    }
                }
            }//bfs 끝

            //물고기 잡을 수 있는지 확인
            if(queue.isEmpty()){
                break; //더이상 먹을 수 있는 물고기가 없다면 엄마찬스
            }
            Fish eat = queue.poll();
            eatFishNum++;
            //아기상어는 자신의 크기와 같은 수의 물고기를 먹을 때마다 크기가 1 증가한다.
            int Size = shark.size;
            if(eatFishNum % shark.size==0){
                Size = shark.size+1;
                eatFishNum = 0;
            }

            shark = new Shark(eat.row,eat.col,Size); //상어는 물고기를 먹은 자리에 가서 서있어야 함

            Map[eat.row][eat.col] = 0; //물고기는 먹혔으므로 0 설정
            fishNum--;

            answer += eat.count; //상어가 이동한 거리는 먹힌 물고기한테 간 거리이기 때문
        }

        System.out.println(answer);
    }

    public static class Shark{
        int row;
        int col;
        int size;
        int count;

        public Shark(int row, int col, int size) {
            this.row = row;
            this.col = col;
            this.size = size;
        }

        public Shark(int row, int col, int size, int count) {
            this.row = row;
            this.col = col;
            this.size = size;
            this.count = count;
        }
    }

    public static class Fish implements Comparable<Fish>{
        int row;
        int col;
        int count;

        public Fish(int row, int col, int count) {
            this.row = row;
            this.col = col;
            this.count = count;
        }

        //거리가 가까운 순, 거리가 가까운 물고기가 많다면 가장 위에 있는 물고기, 그러한 물고기가 여러마리라면 가장 왼쪽에 있는 물고기
        @Override
        public int compareTo(Fish o) {
            int cmp = Integer.compare(count,o.count);
            if(cmp==0){
                cmp = Integer.compare(row,o.row);
                if(cmp==0){
                    cmp = Integer.compare(col,o.col);
                }
            }
            return cmp;
        }
    }
}

[느낀점]

소요시간 : 1h 50min

생각보다 문제를 읽는데 시간이 많이 걸렸다. 그리고 dfs에서 bfs로 생각을 바꾸는데까지도 꽤 많은 시간이 걸렸다. 

추가로 문제 조건 잘못읽어서 한 번에 풀 것을 못풀었다.. 문제 조건 더 꼼꼼히 읽자ㅜㅜ

그리고 bfs쓰긴 했지만, dfs로 짤 때 방문처리 제대로 안했었는데 dfs문제 풀 때 좀 더 주의하자

 

[시간복잡도]

1억에 1초가 걸린다고 한다. 

BFS의 시간복잡도는 O(n^2)이다. (모든 정점 n^2, 정점마다 4방 -> O(4n^2)=O(n^2))

제일 바깥의 while문은 물고기 최대 개수(n^2)만큼 실행되기 때문에 O(n^2)이다. 

=> O(n^4)

n은 20이기 때문에 삽가능이다. (16만 < 1억)