BFS_16236_아기상어

https://www.acmicpc.net/problem/16236

16236번: 아기 상어

문제를 풀기 위한 조건이 많기도 하지만 조건을 맞추기가 굉장히 까다로웠다. 충족해야 하는 조건을 크게 잡아보면 아래와 같다. 

1. 최단거리 탐색 방법
   1. 최단거리하면 떠오르는 알고리즘은 단연 다익스트라가 먼저일 것이다. 하지만 모든 간선의 가중치가 1인 경우에는 더 효율적인 BFS가 있기 때문에, BFS를 활용해서 풀이해보도록 하자.
2. 거리가 같은 경우 우선순위가 높은 물고기를 잡으러 가는 방법
   1. 가장 중요하면서도 기본적인 베이스는 일단 물고기를 먹을 수 있는 상황에서 조건을 검사해야 한다는 것이다.
   2. 먹을 수 있는 물고기가 여러 마리라면 가장 위로 가자 -> x(행)의 좌표가 가장 작은 값
   3. 같은 행의 먹을 수 있는 물고기가 여러 마리라면 가장 왼쪽으로 가자 -> y(열)의 좌표가 가장 작은 값
3. 상어의 성장
   1. 1번의 BFS탐색을 통해서 가장 가까운 곳에 있는 물고기의 위치로 이동해서 물고기를 잡아먹는다. 이때 상어의 위치가 이동하고
   2. 상어가 이동할 때마다 먹은 물고기의 수를 카운트해준다.
   3. 한 번의 BFS가 끝날 때마다 조건을 검사하 되, 먹은 물고기 수가 자신의 사이즈와 같을 때만 성장시킨다.

위의 큰 조건을 기반으로 로직을 구성해보자.

[ 1. 초기화 ]

전역변수로 사용한 내용이 많은데,, 주석을 참고하길 바란다. map의 정보를 받을 때, 아기상어의 위치를 따로 변수에 담아두고, 해당 위치의 값은 9에서 0으로 바꾸어 준다.

public class _16236_아기상어 {
    static int n;                             //map의 크기
    static int eatCnt = 0;                     //아기상어가 먹은 물고기 수
    static int minX, minY, minDist;            //현재 위치에서 이동할 수 있는 최소거리, 그때의 x,y좌표
    static int map[][];                        //탐색을 진행할 map
    static int dist[][];                     //방문 체크 겸 최단 거리 저장 배열
    static int dx[] = {-1, 1,  0, 0};         //상하좌우 이동(x)
    static int dy[] = { 0, 0, -1, 1};         //상하좌우 이동(y)
    static int count=0;                        //아기 상어의 전체 이동 시간
    static int size = 2;                     //초기 아기 상어의 크기
    static int INF = Integer.MAX_VALUE;     //최솟값을 찾기 위한 초깃값
    public static void main(String [] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        
        n = Integer.parseInt(br.readLine());
        map = new int[n][n];
        int sharkX = 0;
        int sharkY = 0;
        for(int i=0; i<n; i++) {
            st = new StringTokenizer(br.readLine());
            for(int j=0; j<n; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
                if(map[i][j] == 9) {//아기 상어의 위치
                    sharkX = i;
                    sharkY = j;
                    map[i][j] = 0;
                }
            }
        }
        
        int time = eatFish(sharkX, sharkY);
        
        System.out.println(time);
        
    }

 

[ 2.물고기 사냥 ]

while반복문이 한 번 돌때마다 아기상어가 물고기를 잡아먹고, 위치가 바뀌었다는 뜻이므로 새로운 BFS탐색을 시작한다. 따라서 탐색에서 필요한 조건을 초기화 해준다. 다음으로 탐색을 하는 과정을 보면 그 쓰임이 명확해지니 일단 이해하자.

탐색이 끝난 후에도 초기화 값이 갱신이 되지 않았다는 것은 아기상어가 최단거리로 도달할 수 있는 물고기가 없다는 것이다. 이 말을 직역하면, 물고기가 아에 없거나 혹은 상어보다 모두 큰 물고기만 있는 경우이다. 이 경우는 바로 무한 루프를 탈출해버린다. 

만약 초기화 값이 갱신 되었다면 적어도 1번은 상어가 물고기를 먹은 것이다. 따라서 물고기를 먹은 위치를 0으로 바꾸어 주고, 그 위치를 상어의 위치(다음 BFS탐색의 시작점)으로 갱신해준다. 여기에서 minDist는 최단거리 즉 아기상어가 물고기를 먹기 위해 이동한 최단시간이 된다.. 

    private static int eatFish(int sharkX, int sharkY) {
        // TODO Auto-generated method stub
        while(true) {
            //방문체크겸 거리배열
            dist = new int[n][n];
            minX = INF;
            minY = INF;
            minDist = INF;
            
            //탐색하면서 거리배열 최신화
            bfs(sharkX, sharkY);
            
            if(minX != INF && minY != INF) {//값이 갱신되었다면 -> 먹을 수 있는 물고기를 찾았다면
                eatCnt++;
                map[minX][minY] = 0;
                sharkX = minX;
                sharkY = minY;
                count += minDist;
                
                if(eatCnt == size) {
                    size++;
                    eatCnt = 0;
                }
            }else {//값이 갱신되지 않았다면 -> 먹을 수 있는 물고기를 찾지 못했다면
                return count;
            }
        }
    }

 

[ 3. BFS탐색 ]

이제 웬만한 조건은 다 잡을 수 있어! 라고 오만했던 필자를 바로 억눌러버렸다.,,, 조건이 복잡하지만 가장 위에서 단계별로 훑어본 내용을 유의깊게 봤다면 금세 이해할 것이다. 

물고기를 먹을 수 있는 상황이 기반이 되었을 때 최단거리에 있는 물고기를 찾아야 한다.

map의 인덱스를 벗어나거나, 아기상어의 크기보다 큰 물고기가 있는 곳이거나, 최단 거리 배열의 값이 0이 아니라면 과감하게 skip한다.

계속해서 거리를 누적해서 BFS탐색을 진행하다가 물고기를 만났는 데(map != 0), 아기상어보다 작다면 -> 먹을 수 있다. 먹을 수 없는 경우에는 계속 해서 큐에 값을 추가하면서 물고기를 찾을 때까지 탐색을 진행한다.

• 물고기의 위치가 최단 거리보다 작다면
  • 최단거리와 그 좌표값을 갱신한다.
• 물고기의 위치가 최단 거리와 동일하다면
  • 거리가 가장 가까운 물고기 중 가장 위에 있는 것을 먹어야 하는데, 대상이 같은 높이(행)에 있다면 
    • 더 왼쪽에 있는 것을 먹고, 그 물고기의 좌표를 상어의 좌표로 넣기 위해 최솟값을 갱신한다.
  • 최단 거리는 같은데, 위치의 높이가 다른 경우 더 위에 있는 물고기를 먹는다.

private static void bfs(int sharkX, int sharkY) {
    // TODO Auto-generated method stub
    Queue<position> q = new LinkedList<position>();
    q.add(new position(sharkX, sharkY));
    
    while(!q.isEmpty()) {
        position now = q.poll();
        
        for(int i=0; i<4; i++) {
            int xx = now.x + dx[i];
            int yy = now.y + dy[i];
            
            
            //배열 범위 밖이면 skip, 물고기가 상어보다 크거나, 이미 최단거리가 표시되어 있으면 skip
            if(xx < 0 || yy < 0 || xx >= n || yy >= n) continue;
            if(map[xx][yy] > size || dist[xx][yy] != 0) continue; 
            
            dist[xx][yy] = dist[now.x][now.y] + 1;
            
            if(map[xx][yy] != 0 && map[xx][yy] < size) {//먹을 수 있는 물고기라면
                
                if(minDist > dist[xx][yy]) {//가장 가까운 거리라면(현재의 최단거리 보다 작다면)
                    minDist = dist[xx][yy];
                    minX = xx;
                    minY = yy;
                    
                }else if(minDist == dist[xx][yy]) {//현재 최단거리와 거리가 동일하다면 -> 거리가 가까운 물고기가 여러마리라면,
                    if(minX == xx) {//가장 위에 있는 물고기가 우선순위가 높은데 이 것도 여러마리라면 가장 왼쪽에 있는 물고기가 우선. -> 값이 더 작을수록 왼쪽에 있다.
                        if(minY > yy) {
                            minX = xx;
                            minY = yy;
                        }
                    }else if(minX > xx) {//가장 위에 있는 물고기가 우선 순위가 높다.
                        minX = xx;
                        minY = yy;
                    }
                }
                
            }
            q.add(new position(xx, yy));
        }
    }
}

 

[ 전체 코드 ]

package BFS;
 
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class _16236_아기상어 {
    static int n;                            //map의 크기
    static int eatCnt = 0;                    //아기상어가 먹은 물고기 수
    static int minX, minY, minDist;            //현재 위치에서 이동할 수 있는 최소거리, 그때의 x,y좌표
    static int map[][];                        //탐색을 진행할 map
    static int dist[][];                    //방문 체크 겸 최단 거리 저장 배열
    static int dx[] = {-1, 1,  0, 0};        //상하좌우 이동(x)
    static int dy[] = { 0, 0, -1, 1};        //상하좌우 이동(y)
    static int count=0;                        //아기 상어의 전체 이동 시간
    static int size = 2;                    //초기 아기 상어의 크기
    static int INF = Integer.MAX_VALUE;    //최솟값을 찾기 위한 초깃값
    public static void main(String [] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        
        n = Integer.parseInt(br.readLine());
        map = new int[n][n];
        int sharkX = 0;
        int sharkY = 0;
        for(int i=0; i<n; i++) {
            st = new StringTokenizer(br.readLine());
            for(int j=0; j<n; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
                if(map[i][j] == 9) {//아기 상어의 위치
                    sharkX = i;
                    sharkY = j;
                    map[i][j] = 0;
                }
            }
        }
        
        int time = eatFish(sharkX, sharkY);
        
        System.out.println(time);
        
    }
    private static int eatFish(int sharkX, int sharkY) {
        // TODO Auto-generated method stub
        while(true) {
            //방문체크겸 거리배열
            dist = new int[n][n];
            minX = INF;
            minY = INF;
            minDist = INF;
            
            //탐색하면서 거리배열 최신화
            bfs(sharkX, sharkY);
            
            if(minX != INF && minY != INF) {//값이 갱신되었다면 -> 먹을 수 있는 물고기를 찾았다면
                eatCnt++;
                map[minX][minY] = 0;
                sharkX = minX;
                sharkY = minY;
                count += minDist;
                
                if(eatCnt == size) {
                    size++;
                    eatCnt = 0;
                }
            }else {//값이 갱신되지 않았다면 -> 먹을 수 있는 물고기를 찾지 못했다면
                return count;
            }
        }
    }
    
    private static void bfs(int sharkX, int sharkY) {
        // TODO Auto-generated method stub
        Queue<position> q = new LinkedList<position>();
        q.add(new position(sharkX, sharkY));
        
        while(!q.isEmpty()) {
            position now = q.poll();
            
            for(int i=0; i<4; i++) {
                int xx = now.x + dx[i];
                int yy = now.y + dy[i];
                
                
                //배열 범위 밖이면 skip, 물고기가 상어보다 크거나, 이미 최단거리가 표시되어 있으면 skip
                if(xx < 0 || yy < 0 || xx >= n || yy >= n) continue;
                if(map[xx][yy] > size || dist[xx][yy] != 0) continue; 
                
                dist[xx][yy] = dist[now.x][now.y] + 1;
                
                if(map[xx][yy] != 0 && map[xx][yy] < size) {//먹을 수 있는 물고기라면
                    
                    if(minDist > dist[xx][yy]) {//가장 가까운 거리라면(현재의 최단거리 보다 작다면)
                        minDist = dist[xx][yy];
                        minX = xx;
                        minY = yy;
                        
                    }else if(minDist == dist[xx][yy]) {//현재 최단거리와 거리가 동일하다면 -> 거리가 가까운 물고기가 여러마리라면,
                        if(minX == xx) {//가장 위에 있는 물고기가 우선순위가 높은데 이 것도 여러마리라면 가장 왼쪽에 있는 물고기가 우선. -> 값이 더 작을수록 왼쪽에 있다.
                            if(minY > yy) {
                                minX = xx;
                                minY = yy;
                            }
                        }else if(minX > xx) {//가장 위에 있는 물고기가 우선 순위가 높다.
                            minX = xx;
                            minY = yy;
                        }
                    }
                    
                }
                q.add(new position(xx, yy));
            }
        }
    }
}
 
class position{
    int x, y;
    public position(int x, int y) {
        this.x = x; 
        this.y = y;
    }
}
/*
    더 작은 크기의 물고기만 먹을 수 있다. 
    같은 크기의 물고기는 지날 수 만 있다. 
    더 큰 크기의 물고기는 지날 수 없다. 
    자신의 크기만큼의 물고리를 먹어야 크기가 증가한다. 3인 경우 3마리를 먹어야 크기 업
    엄마에게 도움없이 얼마의 시간동안 움직일 수 있는가? 
*/