[JAVA] 백준 아기상어

현재상어->음식 길찾기 : 탐색

 

길찾으면서 거리 측정 비교 : 객체로 dist값을 넣어놓는다.

 

맨위,맨왼쪽부터는 for문을 돌려서 왼쪽부터 돌려나가면 된다.

=>(1,1)에서 시작해서 Fish 탐색

 

전체코드를 우선 보겠다.

import java.io.*;
import java.util.*;

class Main {
    public static int N, time, sx, sy, size, count, map[][];
    public static ArrayList<Info> fishes;
    public static int dx[] = {-1, 1, 0, 0};
    public static int dy[] = {0, 0, -1, 1};

    // 상어 또는 물고기의 위치와 거리를 담을 클래스
    static class Info {
        int x, y, dist;

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

    // 맵 범위 체크 메소드
    public static boolean isRange(int x, int y) {
        return x < 0 || x >= N || y < 0 || y >= N;
    }

    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        map = new int[N][N];
        size = 2; // 초기 나이 2로 셋팅

        // 입력으로 주어진 값을 받고 상어가 있는 위치 0으로 초기화
        for (int i = 0; i < N; i++) {
            String input1[] = br.readLine().split(" ");
            for (int j = 0; j < N; j++) {
                int num = Integer.parseInt(input1[j]);
                map[i][j] = num;
                if (num == 9) {
                    sx = i;
                    sy = j;
                    map[i][j] = 0;//0으로 해줘야함.
                }
            }
        }

        while (true) {
            fishes = new ArrayList<Info>(); // 먹을 수 있는 물고기의 정보를 담을 수 있는 ArrayList 생성
            Queue<Info> q = new LinkedList<Info>(); // bfs 수행을 위한 큐 생성
            boolean visited[][] = new boolean[N][N]; // 방문 표시를 하기 위한 boolean 타입의 2차원 배열 생성
            q.offer(new Info(sx, sy, 0)); // 상어의 위치 q에 삽입, 물고기를 먹었으므로 0으로 거리 갱신
            visited[sx][sy] = true; // 방문 표시

            while (!q.isEmpty()) {
                Info shark = q.poll();

                for (int d = 0; d < 4; d++) { // 상하좌우 탐색
                    int nx = shark.x + dx[d];
                    int ny = shark.y + dy[d];

                    if (isRange(nx, ny)) continue; // 범위 체크
                    if (visited[nx][ny]) continue; // 방문했는지 여부 체크
                    // 먹이를 찾은 경우(0보다 크고 상어의 사이즈보다 작은 경우만 먹을 수 있다는 조건)
                    if (1 <= map[nx][ny] && map[nx][ny] < size) {
                        q.offer(new Info(nx, ny, shark.dist + 1)); // 상어의 위치 갱신
                        fishes.add(new Info(nx, ny, shark.dist + 1)); // 먹이 리스트에 삽입
                        visited[nx][ny] = true; //방문 표시
                    }

                    // 먹을 수는 없지만 지나갈 수 있는 경우(0이거나 상어의 사이즈와 같은 경우 지나갈 수 있다는 조건)
                    else if (map[nx][ny] == size || map[nx][ny] == 0) {
                        q.offer(new Info(nx, ny, shark.dist + 1)); // 상어 위치 갱신
                        visited[nx][ny] = true; // 방문 표시
                    }
                }
            }

            // 사이즈가 0인 경우 먹을 수 있는 물고기가 없는 경우이므로 출력
            if (fishes.size() == 0) {
                System.out.println(time);
                return;
            }

            // 먹을 물고기가 있는 경우
            Info eatingFish = fishes.get(0);
            for (int i = 1; i < fishes.size(); i++) {
                if (fishes.get(i).dist < eatingFish.dist) { // 거리가 최소인 물고기로 갱신
                    eatingFish = fishes.get(i);
                }

                if (eatingFish.dist == fishes.get(i).dist) { // 거리가 같은 경우 X가 작은 물고기가 우선순위가 되므로 갱신
                    if (eatingFish.x > fishes.get(i).x) {
                        eatingFish = fishes.get(i);
                    }
                }
            }

            time += eatingFish.dist; // 먹을 물고기의 거리를 time에 추가
            count++; // 먹었으므로 카운트 증가
            map[eatingFish.x][eatingFish.y] = 0; // 물고기를 먹은 자리 0으로 갱신

            if (count == size) { // 먹은 물고기의 수와 상어의 사이즈가 같은 경우
                size++; // 상어의 사이즈 1 증가
                count = 0; // 다시 카운트는 0으로 초기화
            }

            sx = eatingFish.x; // 상어의 위치 갱신
            sy = eatingFish.y; // 상어의 위치 갱신
        }
    }
}

코드출처 : devje8.tistory.com/11

 

두번째 while문은 bfs를 하는 반복문이다.

q가빌때까지(현재위치에서 갈 수 있는 모든 먹이들까지의 bfs경우의수를 queue에 넣어줌) 아래 경우로 나뉘어 작동한다.

1. 지나갈수있는경우(0, size보다작거나 같은 경우)

2. 먹이발견한경우(size보다 큰 경우)

 

이를통해서, q가 끝까지 방문해서 fishes에 먹이위치와 거리를 add한다.

테스트케이스

while문에서 fish찾는것.

1번째시행
fish 0,1
fish 0,0
fish 0,2
fish 0,3
fish 0,4
fish 0,5

2번째시행
fish 0,0
fish 0,2
fish 0,3
fish 0,4
fish 0,5

 

3번째 시행

=> size가 커졌기때문에 fish의 크기가 1인것과 2인것을 모두 찾아서 거리가 가까운것부터 먹는것이다.
fish 1,0
fish 2,0
fish 1,1
fish 0,2
fish 3,0
fish 2,1
fish 0,3
fish 3,1
fish 1,3
fish 0,4
fish 3,2
fish 2,3
fish 1,4
fish 0,5
fish 2,4

 

---

아래부분은 거리가 최소인 물고기를 뽑아서 상어의 위치로 갱신

그리고 가장바깥의 while(true)문을 반복하는 형식이다.

 

이때, 안쪽 while(!q.isEmpty())부분에서 탐색한 먹을수있는 물고기가 단 한마리도 없으면

while(true)에서 break하면서 time을 출력하고 종료한다.