알고리즘 풀이 - 백준 16236(아기 상어, 그래프(BFS))

 

관련글

 

그래프 관련 포스팅은 여기를 참조
DFS 관련 포스팅은 여기를 참조
BFS 관련 포스팅은 여기를 참조

 

 

1. 개요

 

문제의 링크는 여기를 참조

 

문제의 내용은 아래의 더보기를 클릭하여 참조

 

아기 상어가 자신보다 작은 물고기를 먹으며 커갈 수 있을 때, 엄마 상어의 도움이 없이 물고기를 찾아 먹으러 다닐 수 있는 최대의 시간을 구하는 문제

 

 

2. 풀이

 

이 문제는 여러번의 BFS를 통해 해결하는 문제이다.

해결 방법은 다음과 같다.

① 현재 남은 물고기의 위치 중 가장 가까운 위치의 물고기를 찾는다.
  → 해당 물고기들 중 가장 좌측 상단에 있는 물고기를 찾는다.
② 해당 물고기를 먹기 위해 위치로 이동한다.
③ 현재 까지 먹은 물고기의 수가 현재 상어의 크기와 같다면 상어의 크기를 +1 해준다.
④ 남은 물고기가 없거나 먹을 수 있는 물고기가 없을 때까지 위의 상황을 반복한다.

 

즉, BFS를 통해 현재 위치에서 가장 가까운 섭취 가능한 물고기의 위치를 찾고 이동 시킨 뒤, 물고기의 상태를 변화시켜야 한다.

이후 해당 위치로 이동시킨 뒤 BFS를 다시 동작시킨다.

 

즉, 이동 가능한 위치로 지속 이동하며 가장 가까운 물고기를 찾는 BFS를 반복하여 수행하여 문제를 해결할 수 있다.

 

 

3. 코드

 

아래의 코드를 통해 정답을 알아보자.

 

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

public class Main{
    static int n;
    static int[][] map;
    static int current;
    static int fish = 0;
    static int[] dy = {-1, 0, 1, 0};
    static int[] dx = {0, -1, 0, 1};
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        map = new int[n][n];
        
        // 주어진 값들 저장
        StringTokenizer st = null;
        for(int i=0; i < n; i++){
            st = new StringTokenizer(br.readLine());
            for(int j=0; j < n; j++){
                int num = Integer.parseInt(st.nextToken());
                
                // 9는 현재 물고기의 위치
                if(num == 9){
                    current = i * n + j;
                    map[i][j] = 0;
                    continue;
                }
                map[i][j] = num;
                if(num != 0) fish++;
            }
        }
        
        // 가장 긴 시간 동안 먹이를 찾을 수 있는 시간을 반환하여 출력
        int ans = getTime();
        System.out.println(ans);
        br.close();
    }
    
    // 가장 긴 시간 반환
    private static int getTime(){
        Queue<Pos> q = new LinkedList<>();
        q.offer(new Pos(current / n, current % n, 0));
        int time = 0;  // 현재 먹이를 먹으며 이동한 시간
        int ate = 0;   // 먹이를 먹은 양
        int shark = 2; // 현재 상어의 크기
        
        while(!q.isEmpty()){
            // 남은 생선이 없다면 추가 탐색은 필요 없다.
            if(fish == 0) break;
        
            // 가장 가까이 있는 위치의 물고기를 찾아서 저장
            Pos s = getShortest(q.poll(), shark);
            
            // 가까운 물고기가 없는 경우에는 현재 시간 정보 반환
            if(s == null){
                return time;
            // 있는 경우에는 해당 위치에서 다시 탐색을 수행해야 하므로 Queue에 넣는다.
            // 이동한 만큼 시간을 더하고 먹은 물고기의 크기에 따라 상어 크기 또한 변경한다.
            } else {
                q.offer(s);
                time += s.time;
                ate++; // 물고기를 먹는다.
                fish--;
                map[s.y][s.x] = 0; // 물고기 먹었으니 0으로 변경
                
                // 물고기 먹고 자신의 size만큼 먹은 경우 size++
                if(ate == shark){
                    shark++;
                    ate = 0;
                }
            }
        }
        return time;
    }
    
    // 가장 가까운 거리에 있는 물고기를 반환
    private static Pos getShortest(Pos p, int shark){
        boolean[][] visited = new boolean[n][n];
        Queue<Pos> q = new LinkedList<>();
        p.time = 0;
        q.offer(p);
        visited[p.y][p.x] = true;
        
        ArrayList<Pos> list = new ArrayList<>();
        while(!q.isEmpty()){
            Pos c = q.poll();
            
            // 해당 위치가 0이 아니고 현재 상어 크기 보다 작다면
            if(map[c.y][c.x] != 0 && map[c.y][c.x] < shark){
                list.add(c);
                continue;  // 해당 위치가 가장 가까우므로 추가 탐색 불 필요
            }
            
            // 각 방향으로 이동하여 탐색
            for(int i=0; i < 4; i++){
                int ny = c.y + dy[i];
                int nx = c.x + dx[i];
                
                // 범위를 벗어나거나 이미 방문된 경우는 제외 처리
                if(ny < 0 || ny >= n || nx < 0 || nx >= n || visited[ny][nx]) continue;
                
                // 현재 상어보다 크기가 작거나 같아야 이동이 가능하다.
                if(map[ny][nx] <= shark){
                    visited[ny][nx] = true;
                    q.offer(new Pos(ny, nx, c.time+1));
                }
            }
        }
        
        // 현재 탐색된 위치들 중 가장 먼저 이동할 위치를 찾는다.
        // 가장 가까운 거리를 우선으로 하며, 동일한 거리일 시 좌상단에 있는 것을 우선으로 함
        Pos retVal = null;
        
        int idx = Integer.MAX_VALUE;  // 현재 위치를 하나의 수치로 표현
        int t = Integer.MAX_VALUE;    // 현재 위치의 거리
        for(Pos c : list){
            // 더 짧은 거리를 찾은 경우 해당 위치로 업데이트
            if(c.time < t){
                retVal = c;
                idx = c.y * n + c.x;
                t = c.time;
            
            // 같은 거리상인 경우 더 좌상단에 있는 것으로 지정
            } else if(c.time == t){
                int idx2 = c.y * n + c.x;
                if(idx2 < idx){
                    retVal = c;
                    idx = idx2;
                }
            }
        }
        return retVal;
    }
}

class Pos{
    int y;
    int x;
    int time;
    public Pos(int y, int x, int time){
        this.y=y;
        this.x=x;
        this.time=time;
    }
}

 

 

읽어주셔서 감사합니다. 오류가 있으면 지적해주시면 반영하겠습니다.