[백준] no16236: 아기상어

728x90

문제

    /**
     * 0. 처음 아기상어의 크기는 2
     * 1. 아기상어는 자기보다 작은 숫자의 물고기만 잡아먹을 수 있음 (같은 숫자 안됨)
     * 2. 아기상어는 자기와 같거나 작은 숫자의 칸은 지나갈 수 있음
     * 3. 아기상어는 자기와 같은 수만큼 물고기를 잡아먹으면 레벨업
     * 4. 만약 잡아먹을게 많으면 가장 가까운 놈부터
     * 5. 만약 같은 거리면, 위에 있는 애부터
     * 6. 만약 전부 다 위에 있는 같은 거리면, 왼쪽부터
     */

원리

BFS와 우선순위 큐를 이용한 방식

1. BFS를 이용해 4방향 탐색을 진행하며, 한 번 먹이를 먹을 때마다 방문을 초기화 해주는 방식

2. 즉, 물고기를 먹을 때마다 맵을 다시 새로 탐색하는 구조

3. 우선순위큐(PriorityQueue)를 이용해 이동거리가 적은 순->더 위에 있는 순 -> 더 왼쪽에 있는 순으로 대기열 정렬 (즉, 세 옵션 전부 오름차순)

4. 상어 객체에서 이동거리를 count하고, 목표 지점에 도달할 때마다 총 이동거리에 더해주고 초기화 해주는 방식

5. 탈출조건:
  1) 사방향 탐색 반복(제일 안쪽) : 물고기를 먹었을 때
  2) 대기열 탐색 (중간) : 대기열이 비었을 때
  3) 새로운 출발 탐색(제일 바깥) : 다 돌았는데, 먹은 물고기가 없을 때

* 처음 출발지점인 9는 탐색을 위해 0으로 지정해줘야 올바른 탐색이 이루어진다.

풀이방법

변수 설명

1. Exp : 경험치. 즉 이번 레벨에서 먹은 물고기 수
2. Level : 2부터 시작하는 아기상어의 레벨 (레벨과 같은 수의 물고기 잡아 잡수면 레벨업)
3. TotalDist : 총 이동거리 (직전에 물고기 잡아잡순 곳부터 새로 잡아 잡순 곳까지의 이동거리를 추가해줌)
4. 객체의 Count : 이번 이동거리 (직전에 물고기 잡아잡순 곳부터 새로 잡아 잡술 곳까지의 이동거리)

PriorityQueue 설명

다중 삼항 연산자를 사용한 방식으로, 이동거리(오름차순) -> Y좌표(오름차순) -> X좌표(오름차순)

나의 코드 [4번이 최종 코드]

1. 실패코드 : PriorityQueue와 BFS를 이용한 방식

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

public class no16236 {
    /**
     * 0. 처음 아기상어의 크기는 2
     * 1. 아기상어는 자기보다 작은 숫자의 물고기만 잡아먹을 수 있음 (같은 숫자 안됨)
     * 2. 아기상어는 자기와 같거나 작은 숫자의 칸은 지나갈 수 있음
     * 3. 아기상어는 자기와 같은 수만큼 물고기를 잡아먹으면 레벨업
     * 4. 만약 잡아먹을게 많으면 가장 가까운 놈부터
     * 5. 만약 같은 거리면, 위에 있는 애부터
     * 6. 만약 전부 다 위에 있는 같은 거리면, 왼쪽부터
     */
    private static int T;
    private static int[] babyShark;
    private static int[][] Sea;
    private static boolean[][] visited;
    private static int[] ver = {-1, 1, 0, 0};
    private static int[] hor = {0, 0, -1, 1};
//    private static PriorityQueue<Integer> pq = new PriorityQueue<>((a,b)-> a-b); // 더 먹을 물고기 있는지 확인용

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        babyShark = new int[2];

        T = Integer.parseInt(br.readLine()); // 맵의 사이즈
        Sea = new int[T][T];
        visited = new boolean[T][T];
        for(int i=0; i<T ; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine(), " ");
            for(int j=0; j<T ; j++) {
                int temp = Integer.parseInt(st.nextToken());
                Sea[i][j] = temp;
                if(temp==9) {
                    babyShark[0] = i;
                    babyShark[1] = j;
                }
            }
        }

        System.out.println(BFS());
    }

    private static int BFS() {
        PriorityQueue<Baby> pq = new PriorityQueue<>((a, b) -> b.Level - a.Level);
        pq.add(new Baby(babyShark[0], babyShark[1], 2, 0, 0));
        int result = 0;

        while(!pq.isEmpty()) {
            Baby now = pq.poll();

            // 탈출조건??

            for(int move = 0; move < 4; move++) {
                int nextY = now.Y + ver[move];
                int nextX = now.X + hor[move];
                // 맵을 벗어나지 않는 선
                if(0<=nextY && nextY<T && 0<= nextX && nextX < T) {
                    if(Sea[nextY][nextX] == 0 && !visited[nextY][nextX]) {
                        pq.add(new Baby(nextY, nextX, now.Level, now.Exp,now.Count+1));
                        visited[nextY][nextX] = true;
                    }
                    else if(Sea[nextY][nextX] < now.Level && Sea[nextY][nextX] != 0 && !visited[nextY][nextX]) {
                        visited[nextY][nextX] = true;
                        Baby checkedBaby = levelCheck(nextY, nextX, now.Level, now.Exp, now.Count);
                        initializeSea();
                        pq.add(checkedBaby);
                    }
                    else if(Sea[nextY][nextX] == now.Level && !visited[nextY][nextX]) {
                        pq.add(new Baby(nextY, nextX, now.Level, now.Exp, now.Count+1));
                    }
                }
            }
        }
        return result;
    }

    private static Baby levelCheck (int Y, int X, int Level, int Exp, int Count) {
        if(Exp+1 == Level) return new Baby(Y, X, Level+1, 0, Count+1);
        else return new Baby(Y,X,Level, Exp+1, Count+1);
    }

    private static void initializeSea () {
        for(int i=0; i<T;i++) {
            for(int j=0; j<T;j++) {
                if(Sea[i][j]==0) visited[i][j] = false;
            }
        }
    }

    private static class Baby {
        private int Y;
        private int X;
        private int Level;
        private int Exp;
        private int Count;

        public Baby(int y, int x, int level, int exp, int count) {
            this.Y = y;
            this.X = x;
            this.Level = level;
            this.Exp = exp;
            this.Count = count;
        }
    }
}

2. 실패 코드 : BFS를 하되, 각 객체마다 고유 Visited[][]를 주어 체크하고, 결과를 모아 Comparator로 정렬해서 출력하려했으나, 각 객체별 visited를 사용하니 특정 구간을 반복해버리는 딜레마 발생

private static int T;
private static int[] babyShark;
private static int[][] Sea;
private static int[] ver = {-1, 1, 0, 0};
private static int[] hor = {0, 0, -1, 1};

private static List<Result> results;

public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    babyShark = new int[2];
    T = Integer.parseInt(br.readLine()); // 맵의 사이즈
    Sea = new int[T][T];
    for (int i = 0; i < T; i++) {
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        for (int j = 0; j < T; j++) {
            int temp = Integer.parseInt(st.nextToken());
            Sea[i][j] = temp;
            if (temp == 9) {
                babyShark[0] = i;
                babyShark[1] = j;
            }
        }
    }

    BFS();

    Comparator<Result> comparator = Comparator.comparing(Result::getLevel).thenComparing(Result::getExp).thenComparing(Result::getCount);
    if(results.size()==0) System.out.println(0);
    else {
        List<Result> sortedList = results.stream().sorted(comparator).collect(Collectors.toList());
        System.out.println(sortedList.get(0));
    }
}


/**
 * BFS 방식
 *
 * 탈출조건 : 더 크거나 같은 수를 만났을 때 탈출.
 * 1. 각 객체마다 visited 맵을 가진다.
 * 2. 자신보다 크거나 같은 수를 만났을 경우, 현재 레벨과 카운트를 result에 반영할건데, 더 높은 레벨에 더 낮은 카운트일 경우에만 할당
 * 3. 만약 0이 아닌 수 중에 레벨보다 낮은 수를 만나면, 해당 위치는 visited처리하고, 나머지 0은 전부 다시 visited 초기화
 */
private static void BFS() {
    PriorityQueue<Baby> pq = new PriorityQueue<>((a, b) -> b.Level - a.Level);
    results = new ArrayList<>(); // 여기 넣어놓고 나중에 comparator로 정렬해서 결과 얻기 (레벨 내림차순, exp내림차순, count오름차순)
    boolean[][] firstVisited = new boolean[T][T];
    firstVisited[babyShark[0]][babyShark[1]] = true;
    Baby firstBaby = new Baby(babyShark[0], babyShark[1], 2, 0, 0, firstVisited);
    pq.add(firstBaby);

    while (!pq.isEmpty()) {
        Baby now = pq.poll();

        for (int move = 0; move < 4; move++) {
            int nextY = now.Y + ver[move];
            int nextX = now.X + hor[move];
            // 맵을 벗어나지 않는 선
            if (0 <= nextY && nextY < T && 0 <= nextX && nextX < T) {

                // 그냥 통과만 할때
                if (Sea[nextY][nextX] == 0 || (Sea[nextY][nextX] == now.Level && !now.Visited[nextY][nextX])) {
                    boolean[][] nowVisited = copyVisited(now.Visited);
                    nowVisited[nextY][nextX] = true;
                    pq.add(new Baby(nextY, nextX, now.Level, now.Exp, now.Count + 1, nowVisited));
                }
                // 잡아먹을때
                if(Sea[nextY][nextX] != 0 && Sea[nextY][nextX] < now.Level && !now.Visited[nextY][nextX]) {
                    boolean[][] nowVisited = now.Visited;
                    initializeVisited(nowVisited);
                    Baby checkedBaby = levelCheck(nextY, nextX, now.Level, now.Exp, now.Count, nowVisited);
                    pq.add(checkedBaby);
                }

                // 막혔을 때
                if(Sea[nextY][nextX] > now.Level || (Sea[nextY][nextX] == now.Level && now.Visited[nextY][nextX])) {
                    results.add(new Result(now.Level, now.Exp, now.Count));
                }
            }
        }
    }
}

private static Baby levelCheck(int Y, int X, int Level, int Exp, int Count, boolean[][] Visited) {
    boolean[][] nowVisited = copyVisited(Visited);
    nowVisited[Y][X] = true;
    if (Exp + 1 == Level) return new Baby(Y, X, Level + 1, 0, Count + 1, nowVisited);
    else return new Baby(Y, X, Level, Exp + 1, Count + 1,nowVisited);
}

private static boolean[][] copyVisited(boolean[][] visited) {
    boolean[][] newVisited = new boolean[T][T];
    for(int i = 0; i < T ; i++) {
        for(int j = 0; j < T; j++) {
            newVisited[i][j] = visited[i][j];
        }
    }
    return newVisited;
}

private static void initializeVisited(boolean[][] visited) {
    for (int i = 0; i < T; i++) {
        for (int j = 0; j < T; j++) {
            if (Sea[i][j] == 0) visited[i][j] = false;
        }
    }
}

private static class Baby {
    private int Y;
    private int X;
    private int Level;
    private int Exp;
    private int Count;
    private boolean[][] Visited;

    public Baby(int y, int x, int level, int exp, int count, boolean[][] visited) {
        this.Y = y;
        this.X = x;
        this.Level = level;
        this.Exp = exp;
        this.Count = count;
        this.Visited = visited;
    }
}

private static class Result {
    private int Level;
    private int Exp;
    private int Count;

    public Result(int level, int exp, int count) {
        this.Level = level;
        this.Exp = exp;
        this.Count = count;
    }

    public int getLevel() { return this.Level; }
    public int getExp () { return this.Exp; }
    public int getCount() { return this.Count; }
}

3. 실패 코드(?) : PriorityQueue와 BFS를 사용했으며, PriorityQueue 조건 추가

[특정 테스트케이스에서만 더 단거리로 나옴]

private static int T;
private static int[][] Sea;
private static boolean[][] visited;
private static int[] ver = {-1, 0, 0, 1};
private static int[] hor = {0, -1, 1, 0};

public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    int initY = 0;
    int initX = 0;
    T = Integer.parseInt(br.readLine()); // 맵의 사이즈
    Sea = new int[T][T];
    visited = new boolean[T][T];

    for (int i = 0; i < T; i++) {
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        for (int j = 0; j < T; j++) {
            int temp = Integer.parseInt(st.nextToken());
            Sea[i][j] = temp;
            if (temp == 9) {
                initY = i;
                initX = j;
            }
        }
    }

    System.out.println(BFS(initY, initX));
}


/**
 * BFS 방식
 * 탈출조건 : 큐가 비워질 때까지 먹이를 먹은 적이 없으면 반복문 탈출
 */
private static int BFS(int initY, int initX) {
    /**
     * 1. 잡아 먹을때까지 반복 -> 큐가 비워질 때까지 잡아먹은 게 없으면 탈출
     * 2. 방문한적 없으면서 0이거나, 방문한 적 없으면서 같은 숫자면 그냥 통과
     * 3. 잡아먹으면, 0으로 바꾸고, result에 이동거리 저장하고, 큐 flush하고, 레벨보다 낮은 숫자는 방문 해제
     */

    // 첫 시작 세팅
    Shark initShark = new Shark(initY, initX, 2, 0);
    Sea[initY][initX] = 0;
    visited[initY][initX] = true;
    int Exp = 0;

    while(true) {
        // 이동거리가 다르면 -> 이동거리를 비교해서 오름차순
        // 이동거리가 같으면 -> 맵의 위아래 비교
        // 위아래 위치가 다르면 -> 더 높은 위치 순(오름차순)
        // 위아래 위치가 같으면 -> 맵 좌우 비교 (오름차순)
        PriorityQueue<Shark> pq = new PriorityQueue<>((a, b)
                -> a.Count != b.Count ? Integer.compare(a.Count, b.Count) : (a.Y != b.Y ? Integer.compare(a.Y, b.Y) : Integer.compare(a.X, b.X)));
        pq.add(initShark);
        int Eat = 0;
        while (!pq.isEmpty()) {
            Shark now = pq.poll();

            for (int move = 0; move < 4; move++) {
                int nextY = now.Y + ver[move];
                int nextX = now.X + hor[move];

                // 맵을 벗어나지 않는 선
                if (0 <= nextY && nextY < T && 0 <= nextX && nextX < T) {
                    // 방문하지 않았을 경우,
                    if(!visited[nextY][nextX]) {
                        // 다음 위치가 0이거나, 현재레벨과 같은 경우, 먹는건 없이 이동만함
                        if (Sea[nextY][nextX] == 0 || Sea[nextY][nextX] == now.Level) {
                            visited[nextY][nextX] = true;
                            pq.add(new Shark(nextY, nextX, now.Level, now.Count + 1));
                        }
                        // 다음 위치가 먹을 수 있는 물고기면,
                        // 먹은 자리는 0으로 바꾸고,
                        // 이번 레벨에서 먹은 만큼 Eat을 +1 해주고, (즉, 현재 레벨에서 먹은 개수랑 경험치랑은 다를 수 있음)
                        // 먹은만큼 경험치에 추가해주고,
                        // 경험지 기반으로 레벨체크 해주고,
                        // 만약 레벨업 했으면 경험치 초기화 해주고, 최신상태의 아기상어를 업데이트 해주고,
                        // 새로운 탐색을 위해 방문체크 초기화 해주고, 현재 위치는 방문체크해주고,
                        // 가장 가까운 거리를 탐색했으니 대기열에 남은건 Flush해주고, 4방향 좌표 반복 종료
                        else if(Sea[nextY][nextX]!=0 && Sea[nextY][nextX]<now.Level) {
                            Sea[nextY][nextX] = 0;
                            Eat++;
                            Exp += Eat;
                            initShark = levelCheck(Exp, nextY, nextX, now.Level, now.Count);
                            if(initShark.Level!=now.Level) Exp = 0;
                            visited = new boolean[T][T];
                            visited[nextY][nextX] = true;
                            while(!pq.isEmpty()) pq.poll();
                            break;
                        }
                    }
                }
            }
        }
        if(Eat==0) break; // 맵을 전부 탐색했음에도 이번 레벨에서 먹은게 없으면 반복 종료 (더이상 먹을 수 있는게 없다는 뜻)
    }
    return initShark.Count;
}

/**
 * 물고기를 잡아먹고, 만약 경험치가 충분하면 레벨업.
 * 충분하게 못먹었으면 이동거리만 추가
 */
private static Shark levelCheck(int Exp, int Y, int X, int Level, int Count) {
    if (Exp == Level) return new Shark(Y, X, Level + 1, Count + 1);
    else return new Shark(Y, X, Level, Count + 1);
}

/**
 * 아기상어 객체
 */
private static class Shark {
    private int Y;
    private int X;
    private int Level; // 현재 레벨
    private int Count; // 이동 거리

    public Shark(int y, int x, int level, int count) {
        this.Y = y;
        this.X = x;
        this.Level = level;
        this.Count = count;
    }
}

4. 성공 코드 : 원리는 같으나, 방식이 조금 다름

private static int T;
private static int[][] Sea;
private static int[] ver = {-1, 0, 0, 1};
private static int[] hor = {0, -1, 1, 0};

public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    int initY = 0;
    int initX = 0;
    T = Integer.parseInt(br.readLine()); // 맵의 사이즈
    Sea = new int[T][T];

    for (int i = 0; i < T; i++) {
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        for (int j = 0; j < T; j++) {
            int temp = Integer.parseInt(st.nextToken());
            Sea[i][j] = temp;
            if (temp == 9) {
                initY = i;
                initX = j;
                Sea[i][j] = 0;
            }
        }
    }

    System.out.println(BFS(initY, initX));
}


/**
 * BFS 방식
 * 탈출조건 : 큐가 비워질 때까지 먹이를 먹은 적이 없으면 반복문 탈출
 */
private static int BFS(int initY, int initX) {
    Shark shark = new Shark(initY,initX,0); // 상어 객체로서, 대기열에서 나오는 애들을 순차적으로 할당해주며 업데이트 됨
    
    // 첫 시작 세팅
    int Level = 2;
    int Exp = 0; // 먹은 물고기 수
    int TotalDist = 0; // 움직인 총 거리

    while (true) {
        PriorityQueue<Shark> que = new PriorityQueue<>((a, b) ->
                a.Count != b.Count ? Integer.compare(a.Count, b.Count) : (a.Y != b.Y ? Integer.compare(a.Y, b.Y) : Integer.compare(a.X, b.X)));
        boolean[][] visited = new boolean[T][T];

        que.add(new Shark(shark.Y, shark.X, 0)); // 상어 업데이트
        visited[shark.Y][shark.X] = true; // 방문체크

        boolean check = false; // 이번 레벨에 물고기 먹었는지 확인용

        while (!que.isEmpty()) {
             shark = que.poll();

             // 물고기 먹은 경우
            if (Sea[shark.Y][shark.X] != 0 && Sea[shark.Y][shark.X] < Level) {
                Sea[shark.Y][shark.X] = 0;
                Exp++;
                TotalDist += shark.Count; // 이번 여정에 움직인 거리를 총 움직인 거리에 추가
                check = true; // 먹었음
                break; // 반복종료 (== 새로운 출발)
            }

            for (int move = 0; move < 4; move++) {
                int nextY = shark.Y + ver[move];
                int nextX = shark.X +hor[move];

                // 범위를 벗어나지 않고, 방문한적 없고, 지나갈 수 있는 길일 때 -> 이동
                if (nextY >= 0 && nextX >= 0 && nextX < T && nextY < T &&
                        !visited[nextY][nextX] && Sea[nextY][nextX] <= Level) {
                    que.add(new Shark(nextY, nextX, shark.Count + 1));
                    visited[nextY][nextX] = true;
                }
            }
        }

        if (!check) break; // 이번 레벨에서 먹은게 없으면 탐색종료

        if (Level == Exp) { // 경험치가 레벨과 같다면 레벨업
            Level++;
            Exp = 0;
        }
    }

    return TotalDist;
}

/**
 * 아기상어 객체
 */
private static class Shark {
    private int Y;
    private int X;
    private int Count; // 이동 거리

    public Shark(int y, int x, int count) {
        this.Y = y;
        this.X = x;
        this.Count = count;
    }
}

레퍼런스 코드

참고 링크 : https://girawhale.tistory.com/39

728x90

저작자표시 비영리 변경금지 (새창열림)

'알고리즘 저장소 (일반방식과 나만의 풀이) > JAVA' 카테고리의 다른 글

[백준] no14928: 큰 수(BIG) (0)	2023.04.05
[백준] no1271: 엄청난 부자2 (0)	2023.04.03
[백준] no6064: 카잉달력 (0)	2023.03.30
[백준] no17626: Four Squares (0)	2023.03.29
[백준] no11727: 2×n 타일링 2 (0)	2023.03.28

문제

원리

풀이방법

나의 코드 [4번이 최종 코드]

레퍼런스 코드

'알고리즘 저장소 (일반방식과 나만의 풀이) > JAVA' 카테고리의 다른 글

티스토리툴바