[BFS] 아기상어 뚜루루뚜루

백준 16236 아기상어 (삼성 SW 역량테스트 기출)

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

package 아기상어;

import java.util.*;

public class Main {

    static int N;
    static int[][] map;
    static List<Integer> fishs = new ArrayList<>();

    //상,좌,우,하 순서로 탐색(부질없음)
    static int[] dn = {-1, 0, 0, 1};
    static int[] dm = {0, -1, 1, 0};

    static int shark=2;
    static int stomach=0;
    static Position p;

    public static void main(String[] args){

        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();

        map = new int[N+1][N+1];

        for(int i=1; i<=N; i++){
            for(int j=1; j<=N; j++){
                int num = sc.nextInt();

                if(num==9){
                    p = new Position(i, j);
                }else{
                    map[i][j] = num;
                    if(0<num) fishs.add(num);
                }
            }
        }

        System.out.println( loop(p, 0) );

    }


    static int loop(Position pos, int count){
        if( isEnd() ) return count;


        //현 위치에서 탐색시작
        Queue<Position> q = new LinkedList<>();
        q.add(pos);
        int[][] visited = new int[N+1][N+1];
        visited[pos.n][pos.m] = 1;

        int cnt=0;
        while (!q.isEmpty()){

            //한 level탐색--------------------------------------------------------------------------
            PriorityQueue<Position> rFish = new PriorityQueue<>();
            cnt++;
 
            int qSize = q.size();
            for(int l=0; l<qSize; l++){

                Position now = q.poll();

                //4방향 탐색
                for(int i=0; i<4; i++){

                    Position next = new Position(now.n+dn[i], now.m+dm[i]);
                    if( isCanGo(next, visited) ){
 

                        //먹을 수 있는 물고기 후보
                        if( isEatable(next) ){ 
                            rFish.add(next);
                        }

                        q.add(next);
                        visited[next.n][next.m]=1; //방문표시

                    }
                }//4방향 탐색
            }//한 레벨 탐색--------------------------------------------------------------------------

            //우선순위 평가 후 섭취
            if( !rFish.isEmpty() ){  
                eatFish( rFish.peek() );
                return loop(rFish.peek(), count+cnt);
            } 
        }


        //물고기는 남았지만 도달할 수 없으면 이곳까지 오게 된다
        return count;
    }




    static boolean isCanGo(Position pos, int[][] visitied){

        //범위 안인지 체크
        if(pos.n < 1 || N < pos.n || pos.m < 1 || N < pos.m ) return false;

        //방문했던 곳인지 체크
        if( visitied[pos.n][pos.m] == 1) return false;

        //나보다 큰 물고기가 있는지 체크
        if( shark < map[pos.n][pos.m]) return false;

        return true;
    }


    //먹을 수 있는 물고기인가
    static boolean isEatable(Position pos){
        if(0 < map[pos.n][pos.m] && map[pos.n][pos.m]<shark) return true;
        return false;
    }



    //먹을 수 있는 물고기 다 먹었는지
    static boolean isEnd(){

        if(fishs.size()==0) return true; //다처먹음
        else{
            for(int f: fishs) if(f < shark) {
                return false; //먹을 물고기가 있다
            }
        }
        return true; //먹을 게 없으니 엄마에게 핼프
    }



    //냠냠
    static void eatFish(Position pos){

        int fish = map[pos.n][pos.m];

        for(int i=0; i<fishs.size(); i++){
            if(fishs.get(i)==fish){

                //먹은물고기 제거
                fishs.remove(i);
                map[pos.n][pos.m] = 0;

                //성장
                stomach++;
                if(shark==stomach){
                    shark++;
                    stomach=0;
                }
                return;
            }
        }
    }



    static class Position implements Comparable<Position>{
        private int n;
        private  int m;

        Position(int n, int m){
            this.n = n;
            this.m = m;
        }


        //[첫번째기준]: n이 작을수록, [두번째기준]: m이 작을수록
        @Override
        public int compareTo(Position o) {
            if(this.n < o.n) return -1;

            else if(this.n == o.n){
                if(this.m < o.m) return -1;
                return 1;
            }

            return 1;
        }
    }
}

이번에는

map을 벗어나거나 visited확인하는 부분을 각각 따로 함수로 작성해서 만들었는데 괜찮은 방법인 것 같다.

 static boolean isCanGo(Position pos, int[][] visitied){

        //범위 안인지 체크
        if(pos.n < 1 || N < pos.n || pos.m < 1 || N < pos.m ) return false;

        //방문했던 곳인지 체크
        if( visitied[pos.n][pos.m] == 1) return false;

        //나보다 큰 물고기가 있는지 체크
        if( shark < map[pos.n][pos.m]) return false;

        return true;
    }

그리고 if중첩하는 것보다, 역 연산으로 조전체크해서 만족 못하면 종결시켜 버리는게 코드가 깔끔한 것 같다.

틀렸던 부분

1. 문제를 똑바로 안읽어서 한마리 잡아먹을 때마다 크기가 +1커지는 걸로 착각.

2. 탐색순서를 상 좌 우 하  로 하면 우선순위가 해결될 줄 알았는데 이렇게 하면 안됨. 그려보면 2번째 껍질에서 반례 생김. 

//[첫번째기준]: n이 작을수록, [두번째기준]: m이 작을수록
        @Override
        public int compareTo(Position o) {
            if(this.n < o.n) return -1;

            else if(this.n == o.n){
                if(this.m < o.m) return -1;
                return 1;
            }

            return 1;
        }

요렇게 해서 두가지 기준을 한꺼번에 정렬.

오름차순: this가 들어온거보다 작으면 -1

참고: 객체(Object) 정렬

3. 먹을 수 있는 물고기는 있지만 갈 수 없는 경우

3

1  3 0

3 0 0

0 0 9

결과가 0이 나와야 한다.

결과가 2로 나오는 것 때문에 cnt라는 변수를 추가했다.

(3근처까지 가보고 나서야 탐색을 중단하기 때문에 거기까지 가는 2가 count에 추가되어서 잘못된 값이 나왔다)

cnt는 탐색을 시작한 이례 이동한 횟수이다.

결과적으로 찾지를 못했다면 반환하는 count에 cnt를 더하지 않고 반환해야 한다.

static int loop(Position pos, int count){
    if( isEnd() ) return count;


    //현 위치에서 탐색시작
    Queue<Position> q = new LinkedList<>();
    q.add(pos);
    int[][] visited = new int[N+1][N+1];
    visited[pos.n][pos.m] = 1;

    int cnt=0;
    while (!q.isEmpty()){

        //한 level탐색
        PriorityQueue<Position> rFish = new PriorityQueue<>();
        cnt++;
        int qSize = q.size();
        for(int l=0; l<qSize; l++){

            Position now = q.poll();

            //4방향 탐색
            for(int i=0; i<4; i++){

                Position next = new Position(now.n+dn[i], now.m+dm[i]);
                if( isCanGo(next, visited) ){
                    
                    //먹을 수 있는 물고기 후보
                    if( isEatable(next) ){ rFish.add(next); }

                    q.add(next);
                    visited[next.n][next.m]=1; //방문표시

                }
            }//4방향 탐색
        }//한 레벨 탐색

        //우선순위 평가 후 섭취
        if( !rFish.isEmpty() ){
            eatFish( rFish.peek() );
            return loop(rFish.peek(), count+cnt);
        }

    }


    //물고기는 남았지만 도달할 수 없으면 이곳까지 오게 된다
    return count;
}

아~기 상어

상어새끼...