SW 1226번 1227번 미로1, 2 [D4]

DFS를 통하여 길을 탐색한다.

오른쪽, 아래쪽, 왼쪽, 위쪽 순으로 벽(1 - WALL)이 아니고 방문한곳(4 - VISIT)이 아닌 경우에만 탐색을 진행한다.

도착지점(3 - GOAL)을 발견하면 SUCCESS = 1을 대입하여 도착했음을 확인한다.

아래는 전체 소스코드이다.

#include <stdio.h>

#define MAZE_LENGTH 16

#define GOAL 3

#define TESTCASE 10

#define WALL 1

#define VISIT 4

void InitializeMaze();

void PrintMaze();

void CreateMaze();

void DFSExploreMaze(int x, int y);

int T = 0;

int Maze[MAZE_LENGTH][MAZE_LENGTH] = { 1, };

int Success = 0;

int main()

{

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

{

scanf(" %d", &T);

InitializeMaze();

CreateMaze();

DFSExploreMaze(1, 1);

printf("#%d %d\n", i, Success);

}

return 0;

}

//미로 배열 값을 0으로 초기화

void InitializeMaze()

{

for (int i = 0; i < MAZE_LENGTH; i++)

{

for (int j = 0; j < MAZE_LENGTH; j++)

{

Maze[i][j] = 0;

}

}

Success = 0;

}

//미로 배열 생성

void CreateMaze()

{

for (int i = 0; i < MAZE_LENGTH; i++)

{

for (int j = 0; j < MAZE_LENGTH; j++)

{

//INPUT 정수가 공백으로 나누어져있지 않아서 %c로 한글자씩 받아서 int로 변환

int temp = 0;

scanf(" %c", &temp);

Maze[i][j] = temp - 48;

//scanf(" %d", &Maze[i][j]); //이렇게 받으면 에러터짐.

}

}

}

//미로 보기

void PrintMaze()

{

for (int i = 0; i < MAZE_LENGTH; i++)

{

for (int j = 0; j < MAZE_LENGTH; j++)

{

printf("%d", Maze[i][j]);

}

printf("\n");

}

}

void DFSExploreMaze(int x, int y)

{

/*경로 확인시 주석 풀기*/

//printf("\n");

//PrintMaze();

//출구를 찾았을 때

if (Maze[x][y] == GOAL)

{

Success = 1;

}

//해당 지점을 방문했음을 표시

Maze[x][y] = VISIT;

//미로를 탐색한다. (우, 하, 좌, 상 순으로)

//오른쪽

if (Maze[x][y + 1] != WALL  && Maze[x][y + 1] != VISIT)

{

DFSExploreMaze(x, y + 1);

}

//아래쪽

if (Maze[x + 1][y] != WALL && Maze[x+1][y] != VISIT)

{

DFSExploreMaze(x+1, y );

}

//왼쪽

if (Maze[x][y - 1] != WALL && Maze[x][y-1] != VISIT)

{

DFSExploreMaze(x, y - 1);

}

//위쪽

if (Maze[x-1][y] != WALL && Maze[x-1][y] != VISIT)

{

DFSExploreMaze(x-1, y);

}

/*

더이상 탐색할 공간이 없다면 뒤로 돌아간다.

굳이 없어도 되는 부분.

*/

return ;

}

미로 2의 경우

#define MAZE_LENGTH 100 으로 수정하면 동작한다.