[6일차][미로] 주어진 숫자 순서 찾기

- 문제 설명

0    0    0    0    0

0    1    2    0    0

3   6    3    0    0

0    5    4    0    0

0    0    0    0    0

위와 같은 숫자판이 주어졌을때

1234563이란 수열을 주어주면

1부터 시작해서 오른쪽 아래 아래 왼쪽 위쪽 왼쪽을 통해 해당 수열을 만족할 수 있다.

- 입력 예시

3
7 1 2 3 4 5 6 3
5
0 0 0 0 0
0 1 2 0 0
3 6 3 0 0
0 5 4 0 0 
0 0 0 0 0
7 1 2 3 4 5 6 3
5
0 0 0 0 0
0 1 2 0 0
0 6 3 0 0
0 5 4 0 0 
0 0 0 0 0
7 1 2 3 4 5 6 3
5
0 0 0 0 0
0 1 2 0 0
0 6 3 0 0
0 5 4 0 0 
0 0 3 2 1

- 출력 예시

#1 1
#2 0
#3 1

- 코드

#include "stdio.h"

int orderNumber;

int order[11]; // 숫자 순서를 넣는 배열

int N; // n*n 의 n값

int map[11][11]; // 미로 배열

int visit[11][11]; // 미로 방문 표시 배열

void findNumberOrder(int col,int row,int orderCount);

int start[11][2]; // 시작점이 여러개 일 수 있기때문에 배열로 가지고 있기

int startCount; // 시작점의 갯수

int success; // 성공 여부

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

    int T;

    scanf("%d", &T);

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

    {

        scanf("%d",&orderNumber); // 숫자 순서의 갯수

        

        for(int i =1;i<=orderNumber;i++) // 숫자 순서 배열 초기화

        {

            order[i] = 0;

        }

        

        for(int i =1;i<=orderNumber;i++) // 숫자 순서 배열 입력 받음

        {

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

        }

        

        scanf("%d",&N); // n 입력 받음

        

        for(int i=1;i<=N;i++) // 미로, 미로 방문 초기화

        {

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

            {

                map[i][j] = 0;

                visit[i][j] = 0;

            }

        }

        

        startCount =0 ; // 시작점 갯수 초기화

        

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

        {

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

            {

                scanf("%d",&map[i][j]); // 미로 입력 받음

                if(order[1] == map[i][j]) // 시작점인 경우 여러개 저장

                {

                    start[startCount][0] = i;

                    start[startCount][1] = j;

                    startCount++;

                }

            }

        }

        

        for(int i=0;i<startCount;i++) // 시작 점 갯수만큼 돌기

        {

            success = 0; // 성공여부 초기화

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

            {

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

                {

                    visit[i][j] = 0; // 방문 배열 초기화

                }

            }

            findNumberOrder(start[i][0], start[i][1], 1); // 검사

            if(success) // 만약 성공하면 for문 나오기

                break;

        }

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

    }

    return 0;

}

void findNumberOrder(int col,int row,int orderCount)

{

    visit[col][row] = 1; // 현재 칸 방문 표시

    if(orderCount == orderNumber) // 순서 배열을 전부다 찾았으면

        success = 1; // 성공 표시

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

    {

        findNumberOrder(col-1, row, orderCount+1); // 순서 카운트 증가해서 위로 감

    }

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

    {

        findNumberOrder(col, row+1, orderCount+1); // 순서 카운트 증가해서 오른쪽으로 감

    }

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

    {

        findNumberOrder(col+1, row, orderCount+1); // 순서 카운트 증가해서 아래로 감

    }

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

    {

        findNumberOrder(col, row-1, orderCount+1); // 순서 카운트 증가해서 왼쪽으로 감

    }

}