[알고리즘] 백준 16236 아기 상어 -bfs , 시뮬레이션- 자바 코틀린

 

www.acmicpc.net/problem/16236

16236번: 아기 상어

 

귀요미 아기상어 문제입니다.

옛날에 나중에 풀어야지 했다가 이번에 solved 클래스에 있길래 풀어봤습니다.

 

처음에 잘 푼줄 알고 테케돌려보는데 4,5,6 만 틀려서 디버깅 하나하나 다 돌려보며 확인했는데도 맞아서 삽질을 좀 했는데 원인은 모든 물고기 상대로 지나갈 수 있는 건지 알았는데 자신보다 작거나 같은 크기의 물고기만 지나갈 수 있던 거였습니다. 

문제를 잘못읽는 습관이 많은데 조심해야겠습니다. ㅠ

추가로 처음에 dr, dc로 위, 왼쪽 기준으로 돌려지겠지 했는데 안그렇습니다. 그래서 최초 잡아먹은 물고기까지의 이동개수만큼의 물고기를 모두 탐색해서 리스트에 넣어서 우선순위를 비교해줍니다. (밑에 예시를 남겨봤습니다. dr, dc 기준으로하면 밑에 왼쪽게 골라집니다.)

 

풀이 방법은 다음과 같습니다. 

1. 아기상어 위치에서 BFS 돌려서 자기보다 작은 물고기 탐색 (방문안하고 자기보다 같거나 크기작은 물고기만 지나갈 수 있음)

2. 자기보다 작은 물고기 찾으면 리스트에 넣어줌, 이동거리도 tmpMove에 저장해서 이후에 찾는 물고기는 탐색안하게 막아줌

3. 최소거리에서 찾은 물고기를 담은 리스트를 먼저 찾아야하는 상단 왼쪽 기준으로 정렬

4. 우선순위 가장 높은 물고기 잡아먹고 뒷처리

5. 잡아먹은 물고기 있다면(true) 1,2,3,4 반복, 없다면(false) 그만

 

 

[Java]

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

class Main {
    private static int[][] map;
    private static boolean[][] isVisited;
    private static int N;
    private static int sRow;
    private static int sCol;
    private static int answer = 0;
    private static int sharkSize = 2;
    private static int eatSize = 0;
    private static int[] dr = {-1, 0, 0, 1};
    private static int[] dc = {0, -1, 1, 0};

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        map = new int[N][N];
        isVisited = new boolean[N][N];
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                map[i][j] = sc.nextInt();
                if (map[i][j] == 9) {
                    sRow = i;
                    sCol = j;
                }
            }
        }
        while (true) { //5
            if (!bfs(sRow, sCol)) break;
        }
        System.out.println(answer);

    }

    // 1.물고기 탐색
    private static boolean bfs(int r, int c) {
        isVisited = new boolean[N][N];
        isVisited[r][c] = true;
        Queue<Point> queue = new LinkedList<>();
        queue.offer(new Point(r, c, 0));
        ArrayList<Point> eatList = new ArrayList<>(); //잡아먹을 수 있는 물고기 리스트
        int tmpMove = 401; //이동거리( 물고기 먹은 경우의 이동경로 이후로 탐색을 그만하기 위한 flag)
        while (!queue.isEmpty()) {
            Point point = queue.poll();
            for (int i = 0; i < 4; i++) {
                int r2 = point.r + dr[i];
                int c2 = point.c + dc[i];
                if (r2 >= 0 && r2 < N && c2 >= 0 && c2 < N && !isVisited[r2][c2] && tmpMove > point.move && sharkSize >= map[r2][c2]) {//크기가 같거나 작은거만 지나갈 수 있다.
                    isVisited[r2][c2] = true;
                    if (map[r2][c2] < sharkSize && map[r2][c2] != 0) { //2. 아기상어가 먹을 수 있는 물고기
                        eatList.add(new Point(r2, c2, point.move + 1));
                        tmpMove = point.move + 1; //최초로 발견한 물고기 이동거리(이 이동거리보다 큰 거는 탐색 멈춤)
                        break;
                    } else { //계속 탐색이동
                        queue.offer(new Point(r2, c2, point.move + 1));
                    }
                }
            }
        }

        //3. 잡아먹은 물고기가 있다면 우선순위인 놈 잡아먹음(가장 상단인 놈 다음엔 왼쪽 기준)
        eatList.sort((o1, o2) -> {
            if (o1.r == o2.r) {
                return o1.c - o2.c;
            } else {
                return o1.r - o2.r;
            }
        });
        //4. 잡아먹은 물고기 있다면 처리해줌
        if (!eatList.isEmpty()) {
            int r2 = eatList.get(0).r;
            int c2 = eatList.get(0).c;
            eatSize++; //먹은개수 + 1
            answer += (eatList.get(0).move);
            map[r][c] = 0; //처음 자기위치 리셋
            map[r2][c2] = 0; //먹은 물고기 처리
            if (eatSize == sharkSize) { //레벨업 체크
                sharkSize++;
                eatSize = 0;
            }
            sRow = r2;
            sCol = c2;
            return true;
        }
        return false;
    }

    private static class Point {
        int r;
        int c;
        int move;

        Point(int r, int c, int move) {
            this.r = r;
            this.c = c;
            this.move = move;
        }
    }


}

 

 

[Kotlin]

import java.util.*


private lateinit var map: Array<IntArray>
private lateinit var isVisited: Array<BooleanArray>
private var N = 0
private var sRow = 0
private var sCol = 0
private var answer = 0
private var sharkSize = 2
private var eatSize = 0
private val dr = intArrayOf(-1, 0, 0, 1)
private val dc = intArrayOf(0, -1, 1, 0)

fun main(args: Array<String>) {
    val sc = Scanner(System.`in`)
    N = sc.nextInt()
    map = Array(N) { IntArray(N) }
    isVisited = Array(N) { BooleanArray(N) }
    for (i in 0 until N) {
        for (j in 0 until N) {
            map[i][j] = sc.nextInt()
            if (map[i][j] == 9) {
                sRow = i
                sCol = j
            }
        }
    }
    while (true) { //5
        if (!bfs(sRow, sCol)) break
    }
    println(answer)
}

// 1.물고기 탐색
private fun bfs(r: Int, c: Int): Boolean {
    isVisited = Array(N) { BooleanArray(N) }
    isVisited[r][c] = true
    val queue: Queue<Point> = LinkedList()
    queue.offer(Point(r, c, 0))
    val eatList = ArrayList<Point>() //잡아먹을 수 있는 물고기 리스트
    var tmpMove = 401 //이동거리( 물고기 먹은 경우의 이동경로 이후로 탐색을 그만하기 위한 flag)
    while (!queue.isEmpty()) {
        val point = queue.poll()
        for (i in 0..3) {
            val r2 = point.r + dr[i]
            val c2 = point.c + dc[i]
            if (r2 in 0 until N && c2 >= 0 && c2 < N && !isVisited[r2][c2] && tmpMove > point.move && sharkSize >= map[r2][c2]) { //크기가 같거나 작은거만 지나갈 수 있다.
                isVisited[r2][c2] = true
                if (map[r2][c2] < sharkSize && map[r2][c2] != 0) { //2. 아기상어가 먹을 수 있는 물고기
                    eatList.add(Point(r2, c2, point.move + 1))
                    tmpMove = point.move + 1 //최초로 발견한 물고기 이동거리(이 이동거리보다 큰 거는 탐색 멈춤)
                    break
                } else { //계속 탐색이동
                    queue.offer(Point(r2, c2, point.move + 1))
                }
            }
        }
    }
    //3. 잡아먹은 물고기가 있다면 우선순위인 놈 잡아먹음(가장 상단인 놈 다음엔 왼쪽 기준)
    eatList.sortWith(Comparator { o1: Point, o2: Point ->
        return@Comparator if (o1.r == o2.r) {
            o1.c - o2.c
        } else {
            o1.r - o2.r
        }
    })
    //4. 잡아먹은 물고기 있다면 처리해줌
    if (eatList.isNotEmpty()) {
        val r2 = eatList[0].r
        val c2 = eatList[0].c
        eatSize++ //먹은개수 + 1
        answer += eatList[0].move
        map[r][c] = 0 //처음 자기위치 리셋
        map[r2][c2] = 0 //먹은 물고기 처리
        if (eatSize == sharkSize) { //레벨업 체크
            sharkSize++
            eatSize = 0
        }
        sRow = r2
        sCol = c2
        return true
    }
    return false
}

private class Point internal constructor(var r: Int, var c: Int, var move: Int)

 

 

댓글과 공감은 큰 힘이 됩니다. 감사합니다. !!