65. 미로탐색(DFS) (it 취업을 위한 알고리즘 문제풀이 입문 (with C/C++) : 코딩테스트 대비) ★★★☆☆

#include <stdio.h>

using namespace std;

int map[8][8];
int count = 0;

void FindRoute(int x, int y)
{
	if(x == 7 && y == 7)
	{
		count++;
	}
	else
	{
		if(map[x][y+1] == 0)
		{
			if(y+1 < 8)
			{
				map[x][y] = 1;
				FindRoute(x, y+1);
				map[x][y] = 0;	
			}
		}
		
		if(map[x][y-1] == 0)
		{
			if(y-1 > 1)
			{
				map[x][y] = 1;
				FindRoute(x, y-1);
				map[x][y] = 0;	
			}	
		}
		
		if(map[x+1][y] == 0)
		{
			if(x+1 < 8)
			{
				map[x][y] = 1;
				FindRoute(x+1, y);
				map[x][y] = 0;
			}
		}
		
		if(map[x-1][y] == 0)
		{
			if(x-1 > 1)
			{
				map[x][y] = 1;
				FindRoute(x-1, y);
				map[x][y] = 0;
			}
		}
	}
}

int main()
{
	for(int i = 1; i <= 7; i++)
	{
		for(int j = 1; j <= 7; j++)
			scanf("%d", &map[i][j]);
	}
	
	FindRoute(1, 1);
	
	printf("%d", count);
	
	return 0;
}

1. 7 * 7 배열 map, 도착지점에 도달할 수 있는 경우의 수 count 를 선언한다.

2. 현재 위치 (x, y) 에서 상하좌우를 확인하여 0이라면 이동한다. 이동한 후에는 이전의 위치를 1로 바꾸어 다시 돌아가는 경우가 없도록 방지한다.

// 오른쪽으로 이동할 때

if(map[x][y+1] == 0)
{
	if(y+1 < 8) // 7 * 7 배열이기 때문에 크기를 벗어나지 않아야함
	{
		map[x][y] = 1; // 지금의 위치를 1로 만들고
		FindRoute(x, y+1); // 오른쪽으로 이동
		map[x][y] = 0; // 모든 이동이 끝나면 0으로 초기화
	}
}

3. 재귀함수가 모두 끝나고 나면 다시 map[x][y] 를 0으로 만들어주어야 다른 재귀함수에서 다시 길로 인식할 수 있다.

(call by Reference 방식이기 때문)