[8일차][다익스트라] 최소 연료 소비량

- 문제 설명

왼쪽위에서 오른쪽 아래로 감

한번에 갈 수 있는 범위는 위, 오른쪽, 아래, 왼쪽 4가지 방향

한 칸 갈때마다 연료 1소비

높이가 현재보다 높을 경우 높이 차이만큼 연료 1 더 소비

0    1    1   1    0

1    1    0   1    0

0    1    0   1    0

1    0    0   1    1

1    1    1   1    1

위와 같은 경우

0    1    1    1   0

1    1    0   1    0

0    1    0   1    0

1    0    0   1    1

1    1    1   1    1

위와 같이 돌아서 연료가 9 소모 된다.

- 입력

1 // 테스트 케이스

5 // N*N크기

0 1 1 1 0 // 맵 표시

1 1 0 1 0

0 1 0 1 0

1 0 0 1 1

1 1 1 1 1

- 출력

#1 9 // 테스트 케이스, 최소 연료 소비량

- 입력 예시

3
3
0 0 0
0 0 0
0 0 0
5
0 1 1 1 0 
1 1 0 1 0 
0 1 0 1 0 
1 0 0 1 1 
1 1 1 1 1 
5
0 0 0 0 0 
0 1 2 3 0 
0 2 3 4 0 
0 3 4 5 0 
0 0 0 0 0 

- 출력 예시

#1 4
#2 9
#3 8

- 코드

#include "stdio.h"

int N;

int map[1001][1001];

int visit[1001][1001];

void checkMinFuel();

int queue[10000002][2];

int front;

int rear;

int main(int argc, const char * argv[]) {

    int T;

    scanf("%d", &T);

    for(int tc = 1;tc <= T;tc++)

    {

        front = -1;

        rear = -1;

        scanf("%d",&N);

        for (int i = 1; i<=N;i++)

        {

            for(int j=1;j<=N;j++)

            {

                scanf("%d",&map[i][j]); // 맵정보 입력 받음

                visit[i][j] = 0x7fffff; // 초기화

            }

        }

        checkMinFuel();

        printf("#%d %d\n", tc,visit[N][N]);

    }

    return 0;

}

void checkMinFuel()

{

    int startCol = 1;

    int startRow = 1;

    // enqueue

    ++rear;

    queue[rear][0] = startCol;

    queue[rear][1] = startRow;

    visit[startCol][startRow] = 0;

    

    while(front!=rear)

    {

        int col, row, fuel, currentHeight, calFuel, addFuel;

        // dequeue

        ++front;

        col = queue[front][0];

        row = queue[front][1];

        fuel = visit[col][row];

        currentHeight = map[col][row];

        

        if(col-1 >= 1) //위로 갈 수 있으면

        {

            addFuel = 0;

            if(map[col-1][row] - currentHeight > 0)

                addFuel = map[col-1][row] - currentHeight;

            calFuel = fuel + 1 + addFuel;

            if(visit[col-1][row] > calFuel) // 기록되는 값이 최소 값일 경우

            {

                //enqueue

                ++rear;

                queue[rear][0] = col-1;

                queue[rear][1] = row;

                visit[col-1][row] = calFuel;

            }

        }

        if(row+1 <= N) //오른쪽으로 갈 수 있으면

        {

            addFuel = 0;

            if(map[col][row+1] - currentHeight > 0)

                addFuel = map[col][row+1] - currentHeight;

            calFuel = fuel + 1 + addFuel;

            if(visit[col][row+1] > calFuel) // 기록되는 값이 최소 값일 경우

            {

                //enqueue

                ++rear;

                queue[rear][0] = col;

                queue[rear][1] = row+1;

                visit[col][row+1] = calFuel;

            }

        }

        if(col+1 <= N) //아래쪽으로 갈 수 있으면

        {

            addFuel = 0;

            if(map[col+1][row] - currentHeight > 0)

                addFuel = map[col+1][row] - currentHeight;

            calFuel = fuel + 1 + addFuel;

            if(visit[col+1][row] > calFuel) // 기록되는 값이 최소 값일 경우

            {

                //enqueue

                ++rear;

                queue[rear][0] = col+1;

                queue[rear][1] = row;

                visit[col+1][row] = calFuel;

            }

        }

        if(row-1 >=1) // 왼쪽으로 갈 수 있으면

        {

            addFuel =0;

            if(map[col][row-1] - currentHeight > 0)

                addFuel = map[col][row-1] - currentHeight;

            calFuel = fuel + 1 + addFuel;

            if(visit[col][row-1] > calFuel) // 기록되는 값이 최소 값일 경우

            {

                //enqueue

                ++rear;

                queue[rear][0] = col;

                queue[rear][1] = row-1;

                visit[col][row-1] = calFuel;

            }

        }

    }

}

- 코드 2

만약 위처럼 풀었을 경우 bfs(너비우선탐색)으로 하기때문에 시작지점으로 부터 1칸 거리에 있는 위치들이 먼저 visit배열에 기록되게 된다.

따라서 먼저 기록되는 위치의 경우 가는 칸 수가 제일 적은 위치부터 기록되는데, 

만약 칸 수가 적은 대신 비용이 높은경우

그 자리에 비용이 낮은 경우가 오면 계속 갱신이 되서 계산이 많아지게 된다.

이를 해결하기 위해 우선순위 큐를 사용하여 이동한 칸 수도 적고, 연료값도 적은 곳부터 돌면, 

비교는 똑같이 하지만 여러번 같은 자리에 최소값을 갱신하는 계산을 하지 않기때문에 속도가 더 빨라진다.

따라서 우선순위 큐(힙정렬)를 사용하여 푸는 방법 기술

#include "stdio.h"

int N;

int map[1001][1001];

int visit[1001][1001];

void checkMinFuel();

int queue[10000002][2];

int front;

int rear;

int dequeue[2]; // deQ를 했을때 결과를 저장할 배열

void enQ(int col, int row);

void deQ();

int main(int argc, const char * argv[]) {

    int T;

    scanf("%d", &T);

    for(int tc = 1;tc <= T;tc++)

    {

        front = 0;

        rear = 0;

        scanf("%d",&N);

        for (int i = 1; i<=N;i++)

        {

            for(int j=1;j<=N;j++)

            {

                scanf("%d",&map[i][j]); // 맵정보 입력 받음

                visit[i][j] = 0x7fffff; // 초기화

            }

        }

        checkMinFuel();

        printf("#%d %d\n", tc,visit[N][N]);

    }

    return 0;

}

void checkMinFuel()

{

    int startCol = 1;

    int startRow = 1;

    // enqueue

    enQ(startCol, startRow);

    visit[startCol][startRow] = 0;

    

    while(front!=rear)

    {

        int col, row, fuel, currentHeight, calFuel, addFuel;

        // dequeue

        deQ();

        col = dequeue[0];

        row = dequeue[1];

        fuel = visit[col][row];

        currentHeight = map[col][row];

        

        if(col-1 >= 1) //위로 갈 수 있으면

        {

            addFuel = 0;

            if(map[col-1][row] - currentHeight > 0)

                addFuel = map[col-1][row] - currentHeight;

            calFuel = fuel + 1 + addFuel;

            if(visit[col-1][row] > calFuel) // 기록되는 값이 최소 값일 경우

            {

                //enqueue

                enQ(col-1, row);

                visit[col-1][row] = calFuel;

            }

        }

        if(row+1 <= N) //오른쪽으로 갈 수 있으면

        {

            addFuel = 0;

            if(map[col][row+1] - currentHeight > 0)

                addFuel = map[col][row+1] - currentHeight;

            calFuel = fuel + 1 + addFuel;

            if(visit[col][row+1] > calFuel) // 기록되는 값이 최소 값일 경우

            {

                //enqueue

                enQ(col, row+1);

                visit[col][row+1] = calFuel;

            }

        }

        if(col+1 <= N) //아래쪽으로 갈 수 있으면

        {

            addFuel = 0;

            if(map[col+1][row] - currentHeight > 0)

                addFuel = map[col+1][row] - currentHeight;

            calFuel = fuel + 1 + addFuel;

            if(visit[col+1][row] > calFuel) // 기록되는 값이 최소 값일 경우

            {

                //enqueue

                enQ(col+1, row);

                visit[col+1][row] = calFuel;

            }

        }

        if(row-1 >=1) // 왼쪽으로 갈 수 있으면

        {

            addFuel =0;

            if(map[col][row-1] - currentHeight > 0)

                addFuel = map[col][row-1] - currentHeight;

            calFuel = fuel + 1 + addFuel;

            if(visit[col][row-1] > calFuel) // 기록되는 값이 최소 값일 경우

            {

                //enqueue

                enQ(col, row-1);

                visit[col][row-1] = calFuel;

            }

        }

    }

}

void enQ(int col, int row)

{

    // 일단 큐에 넣어줌

    int c = ++rear;

    queue[c][0] = col;

    queue[c][1] = row;

    

    int p = c/2;

    while(c>1 && visit[queue[p][0]][queue[p][1]] >  visit[queue[c][0]][queue[c][1]]) // 자식노드가 연료값이 더 작으면

    {

        //swap

        int tmp = queue[p][0];

        queue[p][0] = queue[c][0];

        queue[c][0] = tmp;

        

        tmp = queue[p][1];

        queue[p][1] = queue[c][1];

        queue[c][1] = tmp;

        

        // 자식이랑 부모 번호 바꿈

        c = p; // 부모번호는 계산하면 되니깐 먼저 자식번호 부터 바꿔줌

        p = c/2;

    }

}

void deQ()

{

    // 맨 첫번째 값을 넣어줌

    dequeue[0] = queue[1][0];

    dequeue[1] = queue[1][1];

    

    // 맨 마지막 노드를 1번 큐(맨 꼭대기)로 올려줌

    queue[1][0] = queue[rear][0];

    queue[1][1] = queue[rear][1];

    rear--; // 마지막을 올려줬으니 마지막 인덱스를 하나 줄여줌

    

    //맨꼭대기니깐 p값을 1로 초기화

    int p = 1;

    while(p <= rear) // p가 마지막이 아닌 동안 반복

    {

        int leftChild = p*2;

        int rightChild = p*2 +1;

        if(rightChild <= rear) // 완벽 이진트리에서 오른쪽 자식노드까지만 존재하는 경우

        {

            // 둘 중 작은 자식노드를 먼저 가져옴

            int minChild = (visit[queue[leftChild][0]][queue[leftChild][1]] <  visit[queue[rightChild][0]][queue[rightChild][1]]) ? leftChild : rightChild;

            if (visit[queue[minChild][0]][queue[minChild][1]] <  visit[queue[p][0]][queue[p][1]]) // 자식노드 값이 부모노드 값보다 작은 경우

            {

                //swap

                int tmp = queue[p][0];

                queue[p][0] = queue[minChild][0];

                queue[minChild][0] = tmp;

                

                tmp = queue[p][1];

                queue[p][1] = queue[minChild][1];

                queue[minChild][1] = tmp;

                

                // 지금은 부모노드랑 자식노드랑 바꿨으므로 p가 자식노드가 됌

                p = minChild;

            }

            else // 부모노드 값이 작은경우

            {

                break; //넘김

            }

        }

        else if(leftChild <= rear) // 완벽 이진트리에서 왼쪽 자식노드까지만 존재하는 경우

        {

            if (visit[queue[leftChild][0]][queue[leftChild][1]] <  visit[queue[p][0]][queue[p][1]]) // 자식노드 값이 부모노드 값보다 작은 경우

            {

                //swap

                int tmp = queue[p][0];

                queue[p][0] = queue[leftChild][0];

                queue[leftChild][0] = tmp;

                

                tmp = queue[p][1];

                queue[p][1] = queue[leftChild][1];

                queue[leftChild][1] = tmp;

                

                // 지금은 부모노드랑 자식노드랑 바꿨으므로 p가 자식노드가 됌

                p = leftChild;

            }

            else // 부모노드 값이 작은경우

            {

                break; //넘김

            }

        }

        else // 얘가 마지막인 경우

        {

            break; // 끝냄

        }

    }

}