90. 라이온킹 심바[BFS]

인프런 - it 취업을 위한 알고리즘 문제풀이 (with C/C++) : 코딩테스트 대비 강의를 바탕으로 공부한 내용입니다.

 

 

풀이 

기존에 풀었던 BFS보다 난이도가 상당하다.

 

1. Loc의 operater

- 최소힙을 이용해 거리가 작은 순으로 정렬

- 심바는 토끼가 여러마리 있을 때 가장 가까운 거리>거리같을때는 위쪽 > 같은 행이라면 왼쪽으로 이동한다.

 

=> 코드의 if문

(1) 거리가 같지 않을 때는 거리가 작은순으로 정렬 

(2) 거리가 같고 행이 다를 경우 위쪽 (x가 작으면 위쪽)

(3)  거리가 같고 행이 같을 시 왼쪽 (y가 작으면 왼쪽)

 

2. map에서 해야할 처리 

(1) 입력을 통해 토끼, 심바의 위치를 받고 9가 입력될 시 simba의 x, y좌표에 i, j값 입력

(2) 이후 해당 좌표는 아무곳도 없는 것과 마찬가지로 0으로 초기화한다.

 

3. 우선순위큐 이용하기

(1) 큐에 심바의 위치와 거리인 0을 넣는다(시작점)

(2) 심바는 좌표만 갖고 있기 때문에 ate, size를 입력한다.(ate=0 / size=2로 문제 제시)

(3) 우선순위 큐에서 거리가 가까운 순으로 하나씩 빼낸다. => tmp

(4) tmp의 x, y, dis를 변수에 담는다. => x, y, dis => map에서 해당 좌표값에 토끼를 먹을 수 있는지 파악 위함

(5) map[x][y]!=0 (토끼가 존재) 이고 해당값이 심바의 사이즈보다 작은 토끼면 먹고 map의 해당값을 0으로 초기화한다

=> ate++ , map[x][y]=0

(6) 먹고 나서는 사이즈만큼 토끼를 먹었으면 사이즈를 업시킨다.

(7)(중요) 한번 먹은 후에는 ch배열을 모두 초기화 하고 우선순위 큐에 들어있는 모든값을 뺸다.

(8) 이후 res를 해당 거리값으로 업데이트 한다.

(9) 해당좌표의 상하좌우를 확인해서 경계 안인지 & 체크가 안된 곳인지 확인한다.

(10) 위의 조건에 부합하면 큐에 해당 좌표를 넣고 ch배열을 업데이트 한다.

 

#include <stdio.h>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
int map[21][21], ch[21][21];
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, 1, 0, -1};
//90. 라이온킹 심바(BFS)

struct Loc
{
    int x;
    int y;
    int dis;
    Loc(int a, int b, int c)
    {
        x = a;
        y = b;
        dis = c;
    }
    bool operator<(const Loc &bb) const
    {
        if (dis != bb.dis)
            return dis > bb.dis;
        if (x != bb.x)
            return x > bb.x;
        else
            return y > bb.y;
    }
};
struct Lion
{
    int x, y, s, ate;
    void sizeUp()
    {
        ate = 0;
        s++;
    }
};

int main()
{
    int n, i, j, res = 0;
    priority_queue<Loc> 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(Loc(simba.x, simba.y, 0));
    simba.s = 2;
    simba.ate = 0;
    while (!Q.empty())
    {
        Loc 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; //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(Loc(xx, yy, z + 1));
            ch[xx][yy] = 1;
        }
    }
    printf("%d\n", res);
    return 0;
}