Baekjoon[16236] - 아기 상어

링크

 

16236번: 아기 상어

문제설명

• 조건에 맞게 이동후 잡아먹고
• 레벨업

문제풀이

• BFS로 거리측정 및 탐색
• Comparator로 위에, 왼쪽인 기준으로 정렬 후 선택

문제코드

package baekjoon;

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Comparator;
import java.util.LinkedList;
import java.util.StringTokenizer;

public class Main16236 {

    static class Comp implements Comparator<int[]>{
        @Override
        public int compare(int[] o1, int[] o2) {
            // TODO Auto-generated method stub
            if(o1[0]!=o2[0]) {
                return o1[0]-o2[0];
            }
            else {
                return o1[1]-o2[1];
            }
        }
    }
    public static Comp comp = new Comp();

    public static int[][] dir = {
            {-1,0},
            {1,0},
            {0,-1},
            {0,1}
    };

    public static int Ans;
    public static int N;
    public static int[][] map;
    public static boolean[][] visited;

    public static void main(String[] args) throws NumberFormatException, IOException {
        System.setIn(new FileInputStream("res/baekjoon/16236.txt"));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        N = Integer.parseInt(br.readLine());
        map = new int[N][N];
        visited = new boolean[N][N];

        LinkedList<int[]> q = new LinkedList<int[]>();
        LinkedList<int[]> fish = new LinkedList<int[]>();

        int[] shark = null;

        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < N; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
                if(map[i][j]==9) {
                    shark = new int[] {i,j,2,0};
                    q.add(new int[] {i,j});
                    visited[i][j]=true;
                    map[i][j]=-1;
                }
            }
        }
        int[] now;
        int qsize;
        int nr;
        int nc;
        int len=0;
        boolean found=false;

        int debug=0;
//        탐색했는데 물고기가 없을 경우
        while(true) {
//        BFS탐색
            len=0;
            found=false;
            visited = new boolean[N][N];
            q.add(new int[] {shark[0],shark[1]});
            visited[shark[0]][shark[1]]=true;
            while(!q.isEmpty()) {
                qsize = q.size();
                for (int i = 0; i < qsize; i++) {
                    now=q.poll();
                    for (int d = 0; d < 4; d++) {
                        nr = now[0] + dir[d][0];
                        nc = now[1] + dir[d][1];
//                    경계 안에서, 방문 안한 칸, 물고기 크기가 나보다 같거나 작으면 탐색가능
                        if(nr>=0 && nr<N && nc>=0 && nc<N && !visited[nr][nc] && map[nr][nc]<=shark[2]) {
                            q.add(new int[] {nr,nc});
                            visited[nr][nc]=true;
//                        먹을 수 있는 물고기 한마리라도 탐지되면
                            if(map[nr][nc]>=1 && map[nr][nc]<shark[2]) {
                                fish.add(new int[] {nr,nc});
                                found=true;
                            }
                        }
                    }
                }
                len++;
                if(found) {
                    fish.sort(new Comparator<int[]>() {
                        @Override
                        public int compare(int[] o1, int[] o2) {
                            // TODO Auto-generated method stub
                            if(o1[0]!=o2[0]) {
                                return o1[0]-o2[0];
                            }
                            else {
                                return o1[1]-o2[1];
                            }
                        }
                    });
                    break;
                }
            }
            if(!found)break;
            int[] move = fish.poll();
            q.clear();
            fish.clear();
//            len만큼 이동후 물고기 먹음
            Ans+=len;
            shark[0] = move[0];
            shark[1] = move[1];
            map[shark[0]][shark[1]]=-1;
            shark[3]++;
//            레벨업
            if(shark[2]==shark[3]) {
                shark[2]++;
                shark[3]=0;
            }
        }
        System.out.println(Ans);
    }
}

아쉬운점

• 인덱스 오류 - shark크기 = shark[2]임 shark[3]이 아니라
• 문제 제대로 안읽음
  • 자기랑 크기가 같은 물고기 못먹음, 미만을 먹을 수 있음.
  • 자기보다 큰 물고기 칸은 지나갈 수 없음.

잘한점

• O(N) = 20*20*N
  • BFS라 굳이?
• Comparator로 정렬 조건맞춰서 구현함
  • Nested Class 말고 static Class로 구현
  • sort를 최대 N번 하므로 nested class호출로 인한 시간 이슈는 무시해도될듯.
  • 실제로 별차이없음