[6일차][미로] 최소합 구하기

- 문제설명

아래와 같은 숫자판

오른쪽이나 아래로만 갈 수 있음

0은 못감

7	4	8	6	8
3	10	0	1	7
6	6	6	9	1

- 입력

숫자는 0~100

줄 수는 3~10

- 출력

#1 34 //테스트케이스, 최소합

- 입력예시

3
3 5
7 4 8 6 8
3 10 0 1 7
6 6 6 9 1
4 5
10 0 1 3 2
7 2 9 8 3
6 9 2 3 9
4 7 0 9 1
5 5
1 10 1 9 0
5 6 9 1 4
8 4 0 2 7
0 2 9 10 0
6 9 3 0 2

- 출력예시

#1 34
#2 43
#3 0

-코드

#include "stdio.h"

int inputCol,inputRow;

int map[11][11];

int visitSum[11][11];

void findMinSum(int startCol,int startRow);

int queue[10001][2];

int front, rear;

int minSum;

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

    int T;

    scanf("%d", &T);

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

    {

        // 큐 초기화

        front = -1;

        rear = -1;

        

        // col, row 입력 받음

        scanf("%d %d",&inputCol,&inputRow);

        

        for(int i =1;i<=inputCol;i++) // 초기화

        {

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

            {

                map[i][j] = 0;

                visitSum[i][j] = 0;

            }

        }

        for(int i =1;i<=inputCol;i++) // 1부터 입력받은 col까지

        {

            for(int j=1;j<=inputRow;j++) // 1부터 입력받은 row까지

            {

                scanf("%d",&map[i][j]);

            }

        }

        minSum = 0x7fffffff; // 최소합 초기화

        findMinSum(1, 1); // 1,1부터 시작

        printf("#%d %d\n",tc,(minSum == 0x7fffffff)?0:minSum); // 최소합이 안바뀌었다면 0, 아니라면 최소합 출력

    }

    return 0;

}

void findMinSum(int col, int row)

{

    visitSum[col][row] = map[col][row]; // 처음 시작위치에 초기값 기록

    

    // enqueue

    ++rear;

    queue[rear][0] = col;

    queue[rear][1] = row;

    

    while (front != rear) {

        // dequeue

        ++front;

        int newCol = queue[front][0];

        int newRow = queue[front][1];

        //        printf("map[%d][%d] = %d\n",newCol,newRow,map[newCol][newRow]);

        

        if(newCol == inputCol && newRow == inputRow) // 끝에 도착하면

        {

            minSum = visitSum[inputCol][inputRow]; // 최소 합을 저장

            return ;

        }

        if(newRow + 1 <= inputRow && map[newCol][newRow+1] != 0) // 우측으로 갈 수 있다면

        {

            // enqueue

            ++rear;

            queue[rear][0] = newCol;

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

            if(visitSum[newCol][newRow+1] == 0) // 만약 처음 들어간다면

            {

                visitSum[newCol][newRow+1] = visitSum[newCol][newRow]+map[newCol][newRow+1]; // 합을 기록

            }

            else // 두번째 들어간다면 기존 합보다 작은 경우만 기록

            {

                visitSum[newCol][newRow+1] = (visitSum[newCol][newRow+1] > visitSum[newCol][newRow]+map[newCol][newRow+1]) ? visitSum[newCol][newRow]+map[newCol][newRow+1] : visitSum[newCol][newRow+1];

            }

        }

        if(newCol + 1 <= inputCol && map[newCol+1][newRow] != 0) // 아래로 갈 수 있다면

        {

            // enqueue

            ++rear;

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

            queue[rear][1] = newRow;

            if(visitSum[newCol+1][newRow] == 0) // 만약 처음 들어간다면

            {

                visitSum[newCol+1][newRow] = visitSum[newCol][newRow]+map[newCol+1][newRow]; // 합을 기록

            }

            else // 두번째 들어간다면 기존 합보다 작은 경우만 기록

            {

                visitSum[newCol+1][newRow] = (visitSum[newCol+1][newRow] > visitSum[newCol][newRow]+map[newCol+1][newRow]) ? visitSum[newCol][newRow]+map[newCol+1][newRow] : visitSum[newCol+1][newRow];

            }

        }

    }

}