[JAVA] [백준] [BFS] 16236. 아기상어

16236. 아기상어

16236번: 아기 상어

 

• 4방탐색 - Node클래스 생성
  • 여기서는 정렬기준에 거리가 속해있기 때문에 x,y뿐만아니라 dist까지 함께 추가
• 📍bfs 함수를 메인의 for문 안에서 반복적으로 호출하는 경우
  • 매번 새로 초기화해줘야하는 변수나 배열 뭔지 확인할 것! 
    • -> 여기서는 fish, visited 매번 초기화
• 자바에서 정렬: Node 클래스 생성시에 implements Comparable<Node> 해주기
  • 정렬 기준 여러개일때 주의할것!!
  • 원하는 정렬기준 순서대로 if(같지않으면) ~ else if() 로 작성하기
  • -> 이후에 Node들어있는 List를 정렬 : Collections.sort(list)

static class Node implements Comparable<Node>{
        int x;
        int y;
        int dist;

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

        //거리 오름차순, x오름차순, y오름차순 정렬
        @Override
        public int compareTo(Node o) {
            if (dist!=o.dist){
                return dist-o.dist;

            }
            else if(x!=o.x){ //dist가 같은데 x는 같지않으면
                return x-o.x;
            } //dist도 같고 x도 같으면
            else return y-o.y;
        }
    }

 

• 전체코드

package com.day20_0307_TopologySort;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class JUN16236_ParkSomin {
    static int N, time, currentX, currentY;
    static int size=2;
    static boolean[][] visited;
    static int[][] map;
    static int[] dx={-1,1,0,0};
    static int[] dy={0,0,-1,1};
    static List<Node> fish;


    //4방탐색 - Node클래스 생성
    static class Node implements Comparable<Node>{
        int x;
        int y;
        int dist;

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

        //거리 오름차순, x오름차순, y오름차순 정렬
        @Override
        public int compareTo(Node o) {
            if (dist!=o.dist){
                return dist-o.dist;

            }
            else if(x!=o.x){
                return x-o.x;
            }
            else return y-o.y;
        }
    }

    public static void main(String[] args) throws IOException {
        //아기상어 시작크기 2
        //상하좌우 이동
        //작거나 같은 물고기 지나감
        //작은 물고기만 먹음
        //거리가 가장 가까운 곳, x작은 곳, y작은 곳
        //이동거리= 시간
        //크기만큼 물고기 먹으면 크기+1
        //물고기 크기 1~6, 상어위치 9

        BufferedReader br= new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st=new StringTokenizer(br.readLine());

        N=Integer.parseInt(st.nextToken());
        map=new int[N][N];


        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){
                    currentX =i;
                    currentY =j;
                    map[i][j]=0; //길을 지나가야하므로 바꿔줘야함
                }
            }
        }

        int cnt=0;
        while (true){
            //fish 랑 visited는 bfs 돌때마다 새로 초기화해줘야함
            fish=new ArrayList<>();
            visited=new boolean[N][N];

            bfs(currentX, currentY);
            Collections.sort(fish); //위에서 정해둔 기준으로 정렬

            if (fish.size()==0){
                System.out.println(time);
                break;
            }

            Node node=fish.get(0); //먹을수 있는 물고기 중 가장 가까운 곳 정보
            int fx=node.x;
            int fy=node.y;
            int fdist=node.dist;

            time+=fdist;
            map[fx][fy]=0; //먹은곳 물고기 제거

            cnt++;
            if(cnt==size){
                size++;
                cnt=0;
            }

            //bfs에 넣을 현재위치 값 바꿔주기
            currentX=fx;
            currentY=fy;
        }
    }

    private static void bfs(int r, int c) {
        Queue<Node> queue=new ArrayDeque<>();
        queue.offer(new Node(r,c,0));
        visited[r][c]=true;

        while(!queue.isEmpty()){
            Node q=queue.poll();
            int x=q.x;
            int y=q.y;
            int dist=q.dist;

            for (int i = 0; i < 4; i++) {
                int nx=x+dx[i];
                int ny=y+dy[i];

                if (nx>=0 && nx<N && ny>=0 && ny<N){
                    //지나갈수 있는 위치(작거나같은곳) 거리계산해두기
                    if(visited[nx][ny]==false && map[nx][ny]<=size){
                        visited[nx][ny]=true;
                        queue.offer(new Node(nx,ny,dist+1));

                        if(map[nx][ny]>=1 && map[nx][ny]<size){ //먹을수있는 물고기 정보
                            fish.add(new Node(nx,ny,dist+1));
                        }
                    }
                }
            }
        }
    }
}

 

---

파이썬 코드 : https://yygs321.tistory.com/318