[백준/19236] 청소년 상어(Java)

Question

• 문제 링크 : https://www.acmicpc.net/problem/19236
• 분류 : DFS
• 풀이 시간 : 120분

문제 해설

1. 물고기 번호 작은 순서대로 이동

   • 이동가능

     • 빈칸일 때
     • 다른 물고기가 있는 칸일 때

   • 이동 불가능

     • 공간 범위 밖일 때
     • 상어가 존재하는 칸일 때

   • 해당 방향에서 이동 못하면 반시계 방향으로 45씩 회전하여 다시 이동 여부 탐색

2. 상어 이동

   • 한번에 여러칸 이동 가능
   • 특정 지점으로 이동 시, 이동 중 만난 물고기 먹지 않음
   • 물고기 먹고, 해당 물고기의 방향 가짐

3. 상어가 이동할 수 있는 칸이 없거나, 공간에서 벗어나면 종료

4. 상어가 먹을 수 있는 물고기 번호의 최댓값은?

Solution

풀이 접근 방법

1. 상어 객체
   • 상어가 위치한 좌표, 방향, 먹은 물고기 번호
2. 물고기 객체
   • 물고기 번호, 물고기가 위치한 좌표, 방향, 생존여부
3. 물고기 이동
   • 물고기가 어디 있는지 확인 : int[][] map 각 위치에 물고기 번호 담음
   • 순서대로 물고기 이동 : 리스트에 물고기를 담아 번호순서대로 오름차순 정렬
     • 정렬한 순서대로 물고기 조회 -> 해당 위치에서 탐색
     • 순서대로 조회 시 죽은 물고기는 탐색하지 않음
4. 상어 이동
   • 먹은 물고기의 합이 최대가 되기 위해 이동할 수 있는 방향 순서대로 DFS

정답 코드

참고 코드