문제

아기 상어가 물고기를 잡아 먹을 수 있는 시간을 구하는 문제

~으아 문제가 정말 길어요~

1. n 공간의 크기 (2 <= n <= 20)

2. 지도의 크기 n n, (1 1 에는 최대 물고기가 1마리 있습니다.)

3. 상어, 물고기 크기는 모두 자연수입니다.

4. 지도 정보
   1) 상어

   • 위치 - 상어의 위치는 숫자 9로 표시됩니다.
   • 크기 - 상어의 크기는 제일 처음에 2 입니다.

   2) 물고기
   크기 - 1, 2, 3, 4, 5, 6: 칸에 있는 물고기의 크기

   3) 빈칸
   빈칸은 0으로 표시됩니다.

5. 이동
   1) 아기 상어는 자신보다 큰 물고기가 있는 칸을 지날 수 없습니다.
   2) 아기 상어는 자신과 같은 크기의 물고기를 먹을 수는 없지만, 그 칸을 이동할 수 있습니다.
   3) 자신의 크기보다 작은 물고기만 먹을 수 있습니다.

6. 크기 증가 조건
   상어가 먹은 물고기의 수가 상어의 크기와 같을 경우 상어의 크기가 1 증가합니다.

7. 먹는 물고기 조건
   1) 가장 이동거리가 짧은 물고기를 먹습니다.
   2) 이동거리가 같은 경우 가장 위쪽에 있는 물고기, 가장 위쪽에 있는 물고기가 여러마리일 경우, 가장 왼쪽에 있는 물고기를 먹습니다.

8. 물고기를 먹으면 빈칸이 되고, 상어가 물고기의 위치로 이동합니다.

9. 다음을 반복합니다.

10. 더 이상 먹을 수 있는 물고기가 없으면 중단합니다.

11. 먹을 수 있는 물고기가 1마리라면, 그 물고기를 먹으러 갑니다.

12. 먹을 수 있는 물고기가 1마리보다 많다면, 거리가 가장 짧은 물고기를 먹습니다.

13. 거리가 가장 짧은 물고기가 여러 마리인 경우, 1) 가장 위쪽, 2) 가장 왼쪽에 있는 물고기를 먹습니다.

• 시간 제한 2초
• 문제 링크

---

풀이 과정

1. 문제 정리

이와 같은 문제일 경우, 1) 문제가 길고, 2) 조건이 많기 때문에 작성하다가 문제 한번 보는 것 처럼 같은 것을 여러번 보느니 천천히 문제를 읽으면서 정리하는것이 좋았습니다.

2. 접근 과정

문제를 풀기 위해 알아야할 내용은 다음과 같습니다.

1) 최단 경로
어떻게 물고기 까지의 최단 거리를 구할 것인가요?

2) 자료구조
어떻게 지도와 위치정보를 저장할 것인가요?

3) 이동
어떻게 상하좌우로 1칸씩 움질인 것인가요?

4) 가장 거리가 짧은 물고기가 여러마리일 경우
어떻게 제일 위쪽, 제일 왼쪽 물고기를 찾을 것인가요?

1) 최단 경로

시작점에서 모든 정점까지의 최단 거리를 계산하는 알고리즘을 최단 경로 알고리즘이라고 합니다.
대표적으로 BFS, 다익스트라 등이 있습니다.
이 문제 에서는 BFS를 사용할 것입니다.
왜냐하면 BFS는 모든 간선의 가중치가 1로 같을때 최단 경로를 찾아줍니다. 또한, 시간 복잡도가 O(v+e) (v는 정점의 수, e는 간선의 수) 로 더 작습니다.

BFS를 사용해서 1) 현재 상어의 위치에서 모든 물고기 까지의 이동 거리를 찾고, 2) 그 중에서 가장 이동 거리가 짧은 물고기를 찾습니다.

2) 자료구조

지도의 정보를 저장하기 위해 2차원 배열을 사용했습니다.
상어 또는 물고기의 x, y좌표를 저장하기 위해 구조체를 사용했습니다.
c++의 경우 pair를 사용하면 더 좋습니다. (비교 연산이 정의 되어 있기 때문)

// 1) 구조제
struct info{
    int x, y;
}

// 2) pair
pair<int, int> info

3) 이동

2차원 배열에서 상하좌우로 이동하는 방법은 다음과 같습니다.

int dx[] = {0, 0, 1, -1};
int dy[] = {-1, 1, 0, 0};

for(int i=0; i<4; i++){
	// x, y는 현재 위치에서의 x, y좌표
    // nx, ny는 상하좌우 위치에서의 x, y좌표로 x또는 y값이 딱 1만큼 변화합니다.
	int nx = x + dx[i];
    int ny = y + dy[i];
}

4) 가장 거리가 짧은 물고기가 여러마리일 경우

저는 if else 구문을 사용해서 다음과 같이 구현했습니다.

// 가장 위쪽에 있다면, 가장 왼쪽에 있는지를 살펴봅니다.
if(min_x == nx){
	if(min_y > ny){
		min_x = nx;
		min_y = ny;
    }
// 가장 위쪽인지 살펴봅니다.
}else if(min_x > nx){
	min_x = nx;
	min_y = ny;
}

3. 시간 복잡도 계산

0) n 제한은 20

1) BFS

모든 정점(n^2), 모든 간선(4n^2) 을 검사합니다. -> O(5n^2), 상수 생략 O(n^2)

2) 반복문

반복문은 최대 먹을 수 있는 물고기의 수 n^2 만큼 수행됩니다. O(n^2)

반복문 * BFS -> O(n^4), n제한이 20이기 때문에 O(n^4)은 16만입니다.
1억에 1초가 걸리고 2초가 주어졌기 때문에 시간안에 충분히 풀 수 있습니다.

코드

1. C++

#include <iostream>
#include <queue>
#include <vector>
#define max_int 21
#define max_val 401

using namespace std;

/*
 시간 복잡도: O(n^4)
 공간 복잡도: O(n^2)
 사용한 알고리즘: BFS(완전 탐색)
 BFS를 사용한 이유는 다음과 같습니다.
 1. 최단 경로를 찾기 위함입니다.
 2. BFS는 모든 간선의 가중치가 1일때 최단경로를 찾아줍니다.
 3. BFS의 시간 복잡도: 1) 인접리스트틀 사용한 경우 O(v+e), 2) 인접행렬을 사용한 경우(v^2)
 
 이 문제에서 그래프를 저장하는 자료구조는 2차원 배열..인접리스트도, 인접행렬도 아닌
 정점의 수 n^2 + 간선의 수 4*n^2 = O(5n^2), 상수 생략 O(n^2)
 사용한 자료구조: 2차원 배열, 큐
 */


// a 배열은 지도의 정보를 저장합니다. check 배열은 이동거리를 저장합니다.
int n, a[max_int][max_int], check[max_int][max_int], shark_x, shark_y, eat_cnt, shark_size = 2;
int min_dist, min_x, min_y, result;

int dx[] = {0, 0, 1, -1};
int dy[] = {-1, 1, 0, 0};

// 상어 또는 물고의 좌표(x, y)를 저장할 구초제 정의
// 가장 위, 가장 왼쪽 비교가 들어가기 때문에
// pair를 사용해도 좋습니다. (pair는 비교를 해주기 때문입니다.)
struct info{
    int x, y;
};

// BFS 수행을 위한 정보 초기화
void init_check(){
    min_dist = max_val;
    min_x = max_int;
    min_y = max_int;
    
    for(int i=1; i<=n; i++){
        for(int j=1; j<=n; j++){
            check[i][j] = -1;
        }
    }
}

// 완전 탐색(BFS) 수행
void bfs(int x, int y){
    // BFS에 사용할 큐를 선언합니다.
    queue<info> q;
    // 상어의 첫 위치의 시간은 0으로 초기화합니다.
    check[x][y] = 0;
    q.push({x, y});
    
    while(!q.empty()){
        // 큐에서 가장 앞에 있는 객체를 꺼냅니다.
        info cur = q.front();
        q.pop();
        int x = cur.x;
        int y = cur.y;
        
        // 4방향을 탐색합니다.
        for(int i=0; i<4; i++){
            int nx = x + dx[i];
            int ny = y + dy[i];
            
            // 지도 밖으로 넘어갔을 경우 건너뜁니다.
            if(nx < 1 || nx > n || ny < 1 || ny > n) continue;
            // 1) 이미 방문했거나, 2) 상어의 크기보다 큰 물고리인 경우 건너 뜁니다.
            if(check[nx][ny] != -1 || a[nx][ny] > shark_size) continue;
            
            // (nx, ny)에 있는 물고기까지의 이동거리를 갱신해줍니다.
            check[nx][ny] = check[x][y] + 1;
            
            // 먹을 수 있는 물고기일 경우
            if(a[nx][ny] != 0 && a[nx][ny] < shark_size){
                
                // 이 부분은 pair의 비교, 객체의 연산자 오버로딩을 통한 <= 비교로 더 간단하게 작성할 수 있습니다.
                // 만약 현재 물고기 까지의 이동시간이 더 짧은 경우
                if(min_dist > check[nx][ny]){
                    min_x = nx;
                    min_y = ny;
                    min_dist = check[nx][ny];
                }
                // 만약 현재 물고기 까지의 이동시간은 같으면 1) 가장 위쪽, 가장 왼쪽을 찾습니다.
                else if(min_dist == check[nx][ny]){
                    if(min_x == nx){
                        if(min_y > ny){
                            min_x = nx;
                            min_y = ny;
                        }
                    }else if(min_x > nx){
                        min_x = nx;
                        min_y = ny;
                    }
                }
            }
            
            // 물고기의 위치를 큐에 넣어줍니다.
            q.push({nx, ny});
        }
    }
}

int main(){
    // 1. 입력
    // 지도 크기를 입력받습니다.
    scanf("%d", &n);
    
    // 지도 정보를 입력받습니다.
    for(int i=1; i<=n; i++){
        for(int j=1; j<=n; j++){
            scanf("%d", &a[i][j]);
            
            // 아기 상어일 경우
            if(a[i][j] == 9){
                // x, y 좌표를 따로 저장해주고
                shark_x = i;
                shark_y = j;
                // 지도상에서 0으로 비워줍니다.
                a[i][j] = 0;
            }
        }
    }
    
    // 2. 반복문 수행
    // 총 n^2(물고기의 총 개수)번 수행됩니다.
    while(true){
        // BFS 수행을 위한 정보 초기화
        init_check();

        // 완전 탐색으로 먹을 수 있는 물고기를 찾습니다.
        bfs(shark_x, shark_y);
        
        // 먹을 수 있는 물고기를 찾은 경우
        if(min_x != max_int && min_y != max_int){
            // 이동시간을 더해줍니다.
            result += check[min_x][min_y];
            
            // 물고기 먹은 수를 1 증가시킵니다.
            eat_cnt++;
            
            // 만약 먹은 물고기 수가 상어의 크기와 같다면
            if(eat_cnt == shark_size){
                // 상어의 크기를 1 증가시키고, 먹은 물고기 수를 0으로 초기화시켜줍니다.
                shark_size++;
                eat_cnt = 0;
            }
            
            // 먹은 물고기의 위치를 0으로 갱신해줍니다.
            a[min_x][min_y] = 0;
            
            // 상어의 위치를 갱신해줍니다.
            shark_x = min_x;
            shark_y = min_y;
        }
        
        // 먹을 수 있는 물고기가 없는 경우 반복문을 끝냅니다.
        else{
            break;
        }
    }
    
    // 3. 출력
    // 이동에 걸린 시간을 출력합니다.
    printf("%d\n", result);
}

2. java

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

/*
시간 복잡도: O(n^4)
공간 복잡도: O(n^2)
사용한 알고리즘: BFS(완전 탐색)
사용한 자료구조: 2차원 배열, 큐
 */

public class Main{

    public static final int max_val = 401, max_int = 21;
    public static int n, shark_x, shark_y, min_dist, min_x, min_y, result, eat_cnt = 0, shark_size = 2;
    public static int [][] a, check;
    public static int [] dx = {0, 0, 1, -1}, dy = {-1, 1, 0, 0};
    public static void main(String args[]) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        n = Integer.parseInt(br.readLine());
        a = new int[n + 1][n + 1];
        check = new int[n+1][n+1];

        for(int i=1; i<=n; i++){
            StringTokenizer st = new StringTokenizer(br.readLine());
            for(int j=1; j<=n; j++){
                a[i][j] = Integer.parseInt(st.nextToken());

                if(a[i][j] == 9){
                    shark_x = i;
                    shark_y = j;
                    a[i][j] = 0;
                }
            }
        }

        while(true){
            init_check();

            bfs(shark_x, shark_y);

            if(min_x != max_int && min_y != max_int){
                result += check[min_x][min_y];

                eat_cnt++;

                if(eat_cnt == shark_size){
                    shark_size++;
                    eat_cnt = 0;
                }

                a[min_x][min_y] = 0;

                shark_x = min_x;
                shark_y = min_y;
            }

            else{
                break;
            }
        }

        System.out.println(result);
    }

    public static void init_check(){
        min_dist = max_val;
        min_x = max_int;
        min_y = max_int;

        for(int i=1; i<=n; i++){
            for(int j=1; j<=n; j++){
                check[i][j] = -1;
            }
        }
    }

    public static void bfs(int x, int y){
        Queue<info> q = new LinkedList<info>();
        check[x][y] = 0;
        q.add(new info(x, y));

        while(!q.isEmpty()){
            info cur = q.poll();
            x = cur.x;
            y = cur.y;

            for(int i=0; i<4; i++){
                int nx = x + dx[i];
                int ny = y + dy[i];

                if(nx < 1 || nx > n || ny < 1 || ny > n) continue;
                if(check[nx][ny] != -1 || a[nx][ny] > shark_size) continue;

                check[nx][ny] = check[x][y] + 1;

                if(a[nx][ny] != 0 && a[nx][ny] < shark_size){

                    if(min_dist > check[nx][ny]){
                        min_x = nx;
                        min_y = ny;
                        min_dist = check[nx][ny];
                    }
                    else if(min_dist == check[nx][ny]){
                        if(min_x == nx){
                            if(min_y > ny){
                                min_x = nx;
                                min_y = ny;
                            }
                        }else if(min_x > nx){
                            min_x = nx;
                            min_y = ny;
                        }
                    }
                }

                q.add(new info(nx, ny));
            }
        }

    }
}

class info{
    int x, y;

    info(int x, int y){
        this.x = x;
        this.y = y;
    }
};