[6일차][미로] 미로 최단거리

-문제 설명

1    1    1    1    1

1    2    0    0    1

1     1    1    0    1

1    3    0    0    1

1    1    1    1    1

1은 벽

2는 시작지점

0은 길

3은 도착

한번에 한칸씩 왼쪽, 위쪽, 오른쪽, 아래쪽으로 갈 수 있다.

- 입력 예시

3
5
11111
12001
10101
13001
11111
5
11111
12131
10111
10001
11111
9
111111111
120000001
101110101
100000101
111110101
101000101
101011101
100000031
111111111

- 출력 예시

#1 1
#2 0
#3 11

- 코드

#include "stdio.h"

int N;

int map[101][101];

int visit[101][101];

void findGoal(int col,int row);

int startCol, startRow;

int goalCol, goalRow;

int queue[10001][2];

int front, rear;

int distance;

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

    int T;

    scanf("%d", &T);

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

    {

        

        scanf("%d",&N); // n*n 배열

        

        // 초기화

        front = -1;

        rear = -1;

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

        {

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

            {

                map[i][j] = 0;

                visit[i][j] = 0;

            }

        }

        // 미로 입력 받기

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

        {

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

            {

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

                if(map[i][j] == 2) // 시작 점 입력

                {

                    startCol = i;

                    startRow = j;

                }

                else if(map[i][j] == 3) // 도착 점 입력

                {

                    goalCol = i;

                    goalRow = j;

                }

            }

        }

        distance = 0; //

        findGoal(startCol, startRow);

        printf("#%d %d\n",tc,(distance != 0) ? distance - 2 : 0 ); // 시작점과 도착점 거리 2를 빼야함

    }

    return 0;

}

void findGoal(int col, int row)

{

    visit[col][row] = 1;

    

    // 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 == goalCol && newRow == goalRow)

        {

            distance = visit[newCol][newRow];

            return ;

        }

        

        if(map[newCol-1][newRow] != 1 && visit[newCol-1][newRow] == 0) // 위로 갈 수 있으면

        {

            // enqueue

            ++rear;

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

            queue[rear][1] = newRow;

            visit[newCol-1][newRow] = visit[newCol][newRow]+1; // 시작거리 보다 1을 더함

        }

        if(map[newCol][newRow+1] != 1 && visit[newCol][newRow+1] == 0) //  오른쪽으로 갈 수 있으면

        {

            // enqueue

            ++rear;

            queue[rear][0] = newCol;

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

            visit[newCol][newRow+1] = visit[newCol][newRow]+1; // 시작거리 보다 1을 더함

        }

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

        {

            // enqueue

            ++rear;

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

            queue[rear][1] = newRow;

            visit[newCol+1][newRow] = visit[newCol][newRow]+1; // 시작거리 보다 1을 더함

        }

        if(map[newCol][newRow-1] != 1 && visit[newCol][newRow-1] == 0) // 왼쪽으로 갈 수 있으면

        {

            // enqueue

            ++rear;

            queue[rear][0] = newCol;

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

            visit[newCol][newRow-1] = visit[newCol][newRow]+1; // 시작거리 보다 1을 더함

        }

    }

}