[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
11101
13001
11111
5
11111
12131
10111
10001
11111
9
111111111
121000001
101111101
100000101
111110101
101000101
101011101
100000031
111111111

- 출력 예시

#1 1
#2 0
#3 1

- 코드

#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 success = 0;

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

    int T;

    scanf("%d", &T);

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

    {

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

        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;

                }

            }

        }

        success = 0;

        findGoal(startCol, startRow); // 미로 찾기

        printf("#%d %d\n",tc,success);

    }

    return 0;

}

void findGoal(int col, int row)

{

    //    printf("map[%d][%d] = %d\n",col,row,map[col][row]);

    visit[col][row] = 1;

    if(col == goalCol && row == goalRow) // 도착점에 도착하면

        success = 1;

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

    {

        findGoal(col-1, row);

    }

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

    {

        findGoal(col, row+1);

    }

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

    {

        findGoal(col+1, row);

    }

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

    {

        findGoal(col, row-1);

    }

}