BOJ 16236 아기상어

BOJ 16236 문제풀이

문제원본

---

문제 설명

주어진 조건

    처음 상어의 크기가 2이고, 상어는 1초에 상하좌우로 이동할 수 있다.

    상어는 자신의 크기보다 작은 물고기만 먹을 수 있다.

    물고기를 자신의 무게 만큼 먹으면 무게가 1씩 증가한다.

    상어는 같은 크기의 물고기는 먹을 수 없지만 같은 크기의 물고기가 있는 칸은 지날 수 있다.

    먹을 수 있는 물고기가 한 마리면 그 물고기가 있는 위치로 이동

    만약 먹을 수 있는 물고기가 여러 마리 라면 가장 가까운 위치로 이동

    거리가 같은 물고기가 많다면 가장 위쪽 이런 경우도 많다면 가장 왼쪽에 있는 물고기를 먹는다.

    먹을 물고기가 없으면 종료한다.

구해야 되는 것

    아기 상어가 주어진 조건에 맞춰 물고기를 먹을때 걸리는 시간

---

문제 풀이

    1 step

        현재 위치에서 도달 가능한 물고기위치의 최소를 전역변수에 저장한다

        전역 변수에는 현재상황에서 최소로 도달 가능한 길이와 좌표가 들어 있다.

    2 step

        아기상어의 위치를 갱신 해주고, 1 step을 더 이상 도달 가능하지 않을 때 까지 반복 시킨다.

 

---

 

해설

    현재 위치에서 한 지점까지의 최단거리 = Dijkstra

소스코드