[ 삼성 SW역량 평가 16326 ] 아기 상어

[ 관련 지식 ]

1.<Vector Library> https://modoocode.com/223

2.<Priority Queue> https://twpower.github.io/93-how-to-use-priority_queue-in-cpp

3.<BFS> https://velog.io/@skyepodium/BFS%EB%8A%94-%EB%82%AF%EC%84%A4%EC%96%B4%EC%84%9C

 

[ 난이도 ]

★★☆

 

[ 문제 링크 ]

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

 

[ 문제 조건 정리 ]

1. N x N 크기의 격자모양 어항에 각 칸에는 최대 1마리의 물고기가 들어갈 수 있다.

2. 0은 물, 9는 상어, 나머지 숫자는 그 숫자만큼의 크기를 갖고 있는 물고기이다.

3. 상어의 초기 크기는 2이며, 자신보다 큰 물고기는 먹을 수 없다. 한 칸 당 1초가 걸린다.

4. 같은 크기의 물고기는 먹을 순 없지만 그 칸을 지날 수는 있다.

5. 먼저 먹는 물고기는 거리가 짧은 순으로 하며 거리가 같다면 위쪽, 그마저도 같다면 왼쪽이 우선순위이다.

6. 상어가 먹을 수 있는 물고기를 다 먹었을 때의 시간을 구하라.

 

[ 문제 풀이 ]

일단 상어가 먹어야 하는 물고기의 거리가 같다면 우선순위를 정해야 하기 때문에 나는 우선순위 큐를

사용하였다 pair<거리,<왼쪽오른,위아래>> 순으로 선언하여 거리가 같을 때 위쪽이나 왼쪽(x,y가 작을때)에 있는

큐를 뽑아야 하므로 Min Hip을 사용하였다.

주로 발생하는 문제의 반례)

1. 상어의 크기가 맵 상의 자신의 숫자(9)를 넘어가는 순간 자기 포식이 일어나는 경우

2. 먹이가 맵상에 존재하지만 가로막힌 경우 

이 경우를 주의하며 코드를 이해해보자.

 

[ 소스 코드 ]

// 헤더파일을 불러옵니다
#include <iostream>
#include <queue>
#include <vector>
#include <functional>
using namespace std;
 
// 받아올수 있는 맵의 최대크기를 선언합니다.
#define Max_Size 21
 
// Map :맵의 정보를 표시, Visit : 큐요소의 방문여부를 결정
int Map[Max_Size][Max_Size];
int Visit[Max_Size][Max_Size];
 
// N : 받아올 맵의 크기
int N; 
 
// 상어의 초기 좌표
int ini_shark_x, ini_shark_y, Fish;
 
// 우선순위큐를 Min Hip으로 만들어줍니다.
priority_queue< pair<int,pair<int, int>>,vector<pair<int, pair<int, int>>>,greater<pair<int, pair<int, int>>>> Q;
 
// 방향을 선언합니다 (dx[0]dy[0] = 북, dx[0]dy[0] = 서, dx[0]dy[0] = 동, dx[0]dy[0] = 남)
int dx[4] = { -1,0,0,1 };
int dy[4] = { 0,-1,1,0 };
 
// Time : 걸린시간, Grow: 먹은 물고기의 횟수
int Time = 0;
int Grow = 0;
 
// Current_Size : 현재 물고기의 크기, 초기 크기가 2이다.
int Current_Size = 2;
 
// BFS를 실행시킬때 그 전의 초기위치를 저장하기 위함.
// 먹이가 있어도 길이 막혀있으면 제자리에서 무한루프를 돌게되는데.
// 그것을 방지해주기 위해 선언한 변수임.
int Pre_inix, Pre_iniy;
 
// (1) 현재 사이즈를 갱신해주는 함수
int Return_Size()
{
    // 먹은 횟수가 현재 크기와 같아진다면 사이즈가 커지며 먹은 횟수는 0으로 초기화됨.
    if (Grow / Current_Size == 1)
    {
        Current_Size++;
        Grow = 0;
    }
    return Current_Size;
}
 
// (2) 현재 맵에 있는 먹을 수 있는 물고기중 가장 작은 사이즈의 물고기의
//       크기를 리턴해줍니다.
int Find_Min_Fish()
{
    int min = 200; // 최솟값을 임의의값(200)으로 초기설정하고 
                   // 더 작은값이 있을때 min값으로 갱신해주는 형식
    for (int i = 1; i <= N; ++i)
    {
        for (int j = 1; j <= N; ++j)
        {
            if (min > Map[i][j] && Map[i][j] != 0) min = Map[i][j];
        }
    }
    return min;
}
 
// (3) BFS를 돌고나면 방문기록과 큐를 모두 초기화 해줌
void Initialize()
{
    // 방문기록 초기화
    for (int i = 1; i <= N; ++i)
    {
        for (int j = 1; j <= N; ++j)
        {
            Visit[i][j] = 0;
        }
    }
    // 큐를 초기화
    while (!Q.empty()) Q.pop();
}
 
// (4) 입력을 받아오고 상어의 위치 까지 알려주는 함수.
void Load_Input()
{
    cin >> N;
    for (int i = 1; i <= N; ++i)
    {
        for (int j = 1; j <= N; ++j)
        {
            cin >> Map[i][j];
            if (Map[i][j] == 9) ini_shark_x = i, ini_shark_y = j;
        }
    }
}
 
// 맵이 상어 9를 제외하고 0으로만 되어있는지(비어있는지)확인하는 함수.
bool Map_Empty()
{
    for (int i = 0; i <= N; ++i)
    {
        for (int j = 0; j <= N; ++j)
        {
            if (Map[i][j] == 9) continue;
            if (Map[i][j] != 0) return false;
        }
    }
    return true;
}
 
// BFS()를 한번 돈다는 의미는 물고기 한마리를 먹는다는 의미이다.
void BFS()
{
    // 큐에 초기조건을 넣습니다.
    Q.push(make_pair(0,make_pair(ini_shark_x,ini_shark_y)));
 
    // 초기위치를 방문표시해줍니다.
    Visit[ini_shark_x][ini_shark_y] = 1;
 
    // 과거값을 갱신해 줍니다.
    Pre_inix = ini_shark_x;
    Pre_iniy = ini_shark_y;
 
    // 큐가 빌 때 까지 탐색을 진행합니다.
    while (!Q.empty())
    {
        // 우선 큐에서 필요한 정보를 얻고 큐를 뺴줍니다
        int x = Q.top().second.first;
        int y = Q.top().second.second;
        int z = Q.top().first;
        Q.pop();
        
        // 종료조건 물고기를 먹을 때 즉 1) 어떤 위치에 갔을때 0이아니며,(2) Size가 상어의 현재크기보다 작고,(3) 자기포식을 막기위해 9가 아닐경우
        if ((Current_Size > Map[x][y] && Map[x][y] != 0) && Map[x][y] != 9 )
        {
            // 처음에 상어가 있던 자리를 0으로 바꿔주고
            Map[ini_shark_x][ini_shark_y] = 0;
            // 새로운 위치에 상어를 놓으며
            Map[x][y] = 9;
            // 먹이를 먹었으므로 먹은수를 1추가 해줌
            Grow++;
            // 초기 위치를 갱신해주고 걸린 시간을 누적시켜줌
            ini_shark_x = x;
            ini_shark_y = y;
            Time = Time + z;
            break;
        }
 
        // 북,서,동,남 순으로 탐색을 한다.
        for (int i = 0; i < 4; ++i)
        {
            // 북 :i[0], 서 : i[1], 동 : i[2], 남 : i[3]
            int nx = x + dx[i];
            int ny = y + dy[i];
 
            // 탐색을 하지 않는 조건)
            if (nx < 1 || nx > N || ny <1 || ny > N) continue; // 1). 맵을 벗어날 경우
            if (Visit[nx][ny] == 1) continue; // 2). 방문기록이 있는 경우
            if (Map[nx][ny] > Current_Size) continue; // 3). 물고기의 크기가 상어보다 클경우
 
            // 탐색을 하면 큐에 넣어주고 방문처리를 한다.
            Q.push(make_pair(z+1,make_pair(nx,ny)));
            Visit[nx][ny] = 1;
        }
    }
}
 
int main()
{    
    // 입력을 받아옵니다.
    Load_Input();
    
    // 물고기를 계속 탐색하고 먹습니다(1물고기당 1BFS)
    while (1)
    {
        // 종료조건1) 맵에 있는 물고기 크기가 현재사이즈 보다 모두크거나 맵이 비어있을경우.
        if (Map_Empty() == true || Find_Min_Fish() >= Current_Size)
        {
            break;
        }
        // 물고기를 계속 반복해서 먹는다.
        BFS();
 
        // 종료조건2) 먹이는 있지만 가로막힌 경우 제자리를 반복하므로 이전과 현재의 시작위치가 같으면 종료
        if (Pre_inix == ini_shark_x && Pre_iniy == ini_shark_y)
        {
            break;
        }
        // 물고기를 1마리 먹고나면 초기화를 해준다.
        Initialize();
 
        // 사이즈를 갱신해준다.
        Return_Size();
    }
    
    // Time을 출력합니다
    cout << Time;
 
    // 시스템을 정상 종료 시킵니다.
    return 0;
}