[Inflearn] 라이언 킹 심바(BFS, priority_queue) (c/c++)

#. Problem

https://www.inflearn.com/course/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

* The copyright in this matter is in Inflearn

#. Resolution Process

  1. Read and understand problem

  2. Redefine the problem + abstract

    - 각 격자에는 토기 한 마리가 있거나 없을 수 있음

    - 심바와 토끼는 모두 몸 크기를 자연수로 가지고 있음

    - 처음 심바의 크기는 2이고 심바는 1초에 인접한 상하좌우 격자칸으로 이동 가능

    - 자신의 몸 크기와 같은 마리수 만큼 잡아먹으면 몸의 크기 1 증가

    - 0은 빈칸이고, 각 토끼의 크기(1, 2, 3, 4, 5, 6, 7)과 9는 심바

   조건)

    - 자신보다 크기가 큰 토끼가 있는 칸은 지나갈 수 없음

    - 자신보다 크기가 작은 토끼만 잡아먹을 수 있음

    - 크기가 같은 토끼는 먹을 수는 없지만 지나갈 수 있음

   

    - 더 이상 먹을 수 있는 토끼가 정글에 없다면 심바는 삼촌 스카에게 복수하러 감

    - 먹을 수 있는 토끼가 딱 한 마리라면, 그 토끼를 먹으러 감

    - 먹을 수 있는 토끼가 두 마리 이상이면, 거리가 가장 가까운 토끼를 먹으러 감

       ㄴ 거리는 최소값

       ㄴ 가까운 토끼가 많으면, 그 중 가장 위쪽에 있는 토끼, 그러한 토끼가 여러 마리라면 가장 왼쪽에 있는 토끼를 

    결과)

    - 몇 초 동안 토끼를 잡아먹고 삼촌 스카에게 복수하러 갈 수 있는지 구하라

  3. Create solution plan (select Algorithm, Data structure)

  4. Prove the plan (check performance time and usage memory)

  5. Carry out the plan

  6. Look back on the plan and find a way to improve it

#. Solve

생각보다 너무 복잡한 문제같다..ㅠㅠ

결국 강사님의 힌트를 얻고 풀어본다..

나중에 문제를 까먹을 때쯤 다시 풀어봐야지.

우선 천천히 과정을 그려보자..?

초기 상황은 아래 그림과 같을 것이다.

거리도 계속 구해줘야하므로 좌표와 같이 갱신해보자.

처음 심바의 위치는 0으로 초기화시켜주고

상우하좌 시계방향으로 토끼가 있는지 탐색하여 queue에 push 해준다.

탐색된 좌표는 ch[][]에 표시해두자.

그런데 queue는 거리 기준으로 priority_queue 를 사용하여야 한다.

이 부분은 구조체에서 구현이 필요할 듯 하다.

가까운 토끼가 많으면, 그 중 가장 위쪽에 있는 토끼, 그러한 토끼가 여러 마리라면 가장 왼쪽에 있는 토끼를 먹는다고 했으니..

먼저 (1, 2) 에 있는 토끼를 먹어보자.

토끼를 먹으면 map[][]에서 그 좌표는 0이 되고, 심바의 좌표도 그 좌표가 된다.

심바가 토끼를 먹었을 경우 일어나는 일을 정리해보면,

1. 토끼가 있던 자리는 map[][] 0으로 수정

2. ch[][] 배열 초기화

3. simba.ate + 1

4. simba.size == simba.ate 일 경우 size + 1, ate = 0

5. queue 비우기

아래 상태가 될 것이다.

이 상태에서 심바의 위치 기준으로 또 탐색을 해보자.

(1, 1) (2, 2) 는 토끼가 없으니 아무 동작을 하지 않고 더 탐색이 필요할 것 같다.

(1, 1) (2, 2) 좌표에서 탐색을 하면서 토끼가 있는 새로운 좌표를 알아냈다.

마찬가지로,

가까운 토끼가 많으면, 그 중 가장 위쪽에 있는 토끼, 그러한 토끼가 여러 마리라면 가장 왼쪽에 있는 토끼를 먹는다고 했던

조건에 의해 위와 같이 queue가 만들어진 것이다.

그럼 (2, 1)로 이동해서 토끼를 먹어보자.

이번에는 simba.size == simba.ate 가 되어 size + 1, ate = 0 동작이 발생할 것이다.

이어서 현재 심바의 위치에서 다시 탐색을 시작해보자.

탐색을 하다보면 map[][]이 0일 경우는 다음 좌표를 탐색하고 queue에 push 해준다.

priority queue 의 순서는 거리값이 같은 경우, 위에 있는 좌표가 우선, 그 다음 왼쪽에 있는 좌표가 우선이 된다.

계속 탐색을 하다가 map[][]이 1일 경우, 

마찬가지로 동작을 수행한다

1. 토끼가 있던 자리는 map[][] 0으로 수정

2. ch[][] 배열 초기화

3. simba.ate + 1

4. simba.size == simba.ate 일 경우 size + 1, ate = 0

5. queue 비우기

현재 심바는 (2, 3, 5) 의 정보를 가지고 있으므로 

(2, 3) 부터 또 탐색을 시작한다.

여기서 (1, 3) 좌표에는 크기가 3인 토끼가 있지만 잡아먹을 수 없고 지나가기만 할 수 있다.

(3, 3) 에서 토끼를 잡아먹게 된다.

이제 또 (3, 3) 좌표에서 먹을 토끼를 탐색해보자!

(3, 2)에서 토끼를 잡아먹게 된다.

이와 같은 과정으로 진행하다보면

(1, 3, 10) 으로 탐색이 끝나게 될 것이다.

그림과 글로 과정을 표현하는게 너무 복잡해서ㅋㅋㅋ

중간에 실수가 있을 수도 있을 것 같지만..

무튼 이런 과정으로 동작하게 된다.

#. Code

line 108에 심바의 size보다 큰 경우에는 priority queue에 들어가지 않도록 해야하는데,

이 조건을 놓치고 있다가 계속 답이 잘못 나와서 헤매고 있었다..

오히려 이렇게 아주 작은 실수가 시간을 엄청 잡아먹는것 같다.

발견하기도 쉽지 않고...

#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
#define f first
#define s second
#define MAX 2147000000
#define MIN -2147000000
 
int map[26][26], ch[26][26], res = 0;
int dx[4] = { -1, 0, 1, 0 };
int dy[4] = { 0, 1, 0, -1 };
 
struct State
{
    int x, y, dist;
 
    State(int a, int b, int c)
    {
        x = a;
        y = b;
        dist = c;
    }
 
    bool operator<(const State &s) const
    {
        if (dist != s.dist) 
            return dist > s.dist;
        if (x != s.x)
            return x > s.x;
        else
            return y > s.y;
    }
};
 
struct Simba
{
    int x, y, size, ate;
 
    void sizeUp()
    {
        size++;
        ate = 0;
    }
};
 
int main(void)
{
    freopen("input.txt", "rt", stdin);
 
    int n, i, j;
    priority_queue<State> pq;
    Simba simba;
    
    scanf("%d", &n);
    for (i = 1; i <= n; i++)
    {
        for (j = 1; j <= n; j++)
        {
            scanf("%d", &map[i][j]);
 
            if (map[i][j] == 9)
            {
                simba.x = i;
                simba.y = j;
                map[i][j] = 0;
            }
        }
    } 
 
    simba.size = 2;
    simba.ate = 0;
    pq.push(State(simba.x, simba.y, 0));
    
    while (!pq.empty())
    {
        State tmp = pq.top();
        pq.pop();
 
        if (map[tmp.x][tmp.y] != 0 && map[tmp.x][tmp.y] < simba.size)
        {
            map[tmp.x][tmp.y] = 0;
            simba.ate++;
 
            simba.x = tmp.x;
            simba.y = tmp.y;
 
            if (simba.ate == simba.size)
                simba.sizeUp();
 
            for (i = 1; i <= n; i++)
                for (j = 1; j <= n; j++)
                    ch[i][j] = 0;
 
            while (!pq.empty())
                pq.pop();
 
            res = tmp.dist;
        }
 
        for (i = 0; i < 4; i++)
        {
            int xx = tmp.x + dx[i];
            int yy = tmp.y + dy[i];
 
            if (ch[xx][yy] == 0 && xx >= 1 && xx <=n && yy >= 1 && yy <= n 
                && map[xx][yy] <= simba.size)
            {
                pq.push(State(xx, yy, tmp.dist + 1));
                ch[xx][yy] = 1;
            }
        }
    }
 
    printf("%d\n", res);
 
    return 0;
}

line 11) 토끼와 심바의 위치를 표시하는 map[][]과 

          심바가 좌표를 탐색하는 과정에서 방문한 곳을 체크하기 위한 ch[][]

line 12~13) 심바가 상하좌우로 이동하기 위한 좌표

line 15~35) 좌표의 상태를 나타내는 구조체

line 17) x, y 좌표와 현재까지 이동거리를 저장하는 변수

line 19~24) State 구조체의 생성자

line 26~34) 아래 조건을 충족시키기 위한 operator

              가까운 토끼가 많으면, 그 중 가장 위쪽에 있는 토끼, 그러한 토끼가 여러 마리라면 가장 왼쪽에 있는 토끼를 먹는다

line 28~29) 가까운 거리가 priority queue의 top에 오도록

line 30~31) 거리가 같지만 x좌표가 다른 경우, 가장 왼쪽 좌표를 반환

line 32~33) x좌표가 다를 경우, 가장 위쪽 좌표를 반환

line 37~46) 심바의 정보를 저장하기 위한 구조체

line 39) 심바의 좌표와 size, 먹은 토끼의 마리 수를 저장하는 변수

line 41~45) 심바의 성장. size가 증가하고 ate 는 0으로 초기화

line 57~70) 정글의 정보를 입력받으면서 심바의 위치가 입력되면,

               심바의 위치를 저장하고 좌표는 0으로 수정

line 72~73) 심바의 size와 먹은 토끼의 마리 수 초기화

line 74) 심바의 초기 위치를 priority queue에 push

line 76~114) queue가 빌 때까지 반복

line 78~79) priority queue의 top을 반환하고 pop

line 81~100) 먹을 수 있는 토끼가 해당 좌표에 있을 경우,

                (=좌표가 0이 아니고(토끼가 있는 경우), 토끼 사이즈가 심바의 사이즈가 작을 경우)

line 83~87) 토끼를 먹었으니 좌표에는 0으로 수정, 심바의 먹을 토끼 수 ++

    심바의 좌표 갱신

line 89~90) 심바가 먹은 토끼의 수가 size와 같아졌다면 심바 sizeUp!

line 92~94) 심바가 좌표를 갱신하였으므로 다시 정글을 탐색해야한다. 그러므로 ch[][] 배열도 초기화

line 96~97) 마찬가지로 심바가 좌표를 갱신하였으므로 priority queue도 초기화

line 99) 현재까지의 거리를 res 변수에 저장

line 102~113) 먹을 수 있는 토끼가 해당 좌표에 없을 경우, 상하좌우를 탐색

line 104~105) 탐색한 좌표 정보를 저장

line 107~112) 방문하지 않은 지점이고 정글 범위 안에 들어오고 map[][] 원소가 심바의 size보다 작거나 같다면 

  해당 좌표와 거리+1 정보를 priority queue에 push 해주고, 방문 체크를 해준다.

#. Other code

#include<stdio.h>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;
 
int map[21][21], ch[21][21];
int dx[4]={-1, 0, 1, 0};
int dy[4]={0, 1, 0, -1};
 
struct State{
    int x, y, dis;
    State(int a, int b, int c){
        x=a;
        y=b;
        dis=c;
    }
    bool operator<(const State &b)const{
        if(dis!=b.dis) return dis>b.dis;
        if(x!=b.x) return x>b.x;
        else return y>b.y;
    }
};
 
struct Lion{
    int x, y, s, ate;
    void sizeUp(){
        ate=0;
        s++;
    }
};
    
int main(){
    freopen("input.txt", "rt", stdin);
 
    int n, i, j, res=0;
    priority_queue<State> Q;
    Lion simba;
 
    scanf("%d", &n);
    for(i=1; i<=n; i++){
        for(j=1; j<=n; j++){
            scanf("%d", &map[i][j]);
 
            if(map[i][j]==9){
                simba.x=i;
                simba.y=j;
                map[i][j]=0;
            }
        }
    }
 
    Q.push(State(simba.x, simba.y, 0));
    simba.s=2;
    simba.ate=0;
 
    while(!Q.empty()){
        State tmp=Q.top();
        Q.pop();
        int x=tmp.x;
        int y=tmp.y;
        int z=tmp.dis;
 
        if(map[x][y]!=0 && map[x][y]<simba.s){    
            simba.x=x;
            simba.y=y;
            simba.ate++;
 
            if(simba.ate>=simba.s) simba.sizeUp();
            map[x][y]=0;
 
            for(i=1; i<=n; i++){
                for(j=1; j<=n; j++){
                    ch[i][j]=0;
                }
            }
            while(!Q.empty()) Q.pop();
 
            res=tmp.dis;
        }
 
        for(i=0; i<4; i++){
            int xx=x+dx[i];
            int yy=y+dy[i];
 
            if(xx<1 || xx>n || yy<1 || yy>n || map[xx][yy]>simba.s || ch[xx][yy]>0) continue;
 
            Q.push(State(xx, yy, z+1));
            ch[xx][yy]=1;        
        }
    }
 
    printf("%d\n", res);
    return 0;
}

강사님의 힌트를 보고 풀어서 로직은 같다.

힌트를 받고라도 풀어서 다행이다..

이렇게 조건이 많고 복잡한 문제도 많이 풀어봐야지..!

#. Result

  - Input --------------------------------------------------------

3

0 1 3

1 9 1

0 1 1

------------------------------------------------------------------

  - Output --------------------------------------------------------

10

------------------------------------------------------------------