n진트리, 4 방향으로 이동경로 출력

1.문제상황

h = 1, w = 1 에서 출발하여 ↑,→,↓,←  4방향으로 움직이며 h = n, w= n 에 도착하여야 한다.한 칸 움직일 때마다 +1을 하며 경로를 표시한다. 1 ≤ h  ≤ n, 1  ≤ w  ≤n 이어야 한다.가능한 모든 경우를 

 

이와 같은 형태로 출력한다.

 

2. 코드

 

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#define n  5  //n은 5로 설정하였다. 다른 수로 설정해도 무방하다.
int A[6][6] = { 0 };


void q(int h, int w, int L) {
	//제한 : 1 <= h <= n, 1 <= w <= n 이어야 하므로
	if (h > n ||h<1|| w > n || w<1)return;
	//이미 지나간 곳은 지나갈 수 없다.
	if (A[h][w] != 0)return;
    //현재 위치에 경로 표시
	A[h][w] = L;
	
	//출력조건 : h == n, w == n 일 때 출력한다.
	if (h == n && w == n) {
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				printf("%3d", A[i][j]);
			}
			printf("\n");
		}
		printf("\n");
		//리셋 : 리턴하기 전 현재 위치에서 전 위치로 돌아가므로 현재 위치는 경로에서 지운다.
		A[h][w] = 0;
		return;
	}

	//n진 트리 : 상, 하, 좌, 우 네 방향으로 움직이므로 4진 트리이다.
	q(h + 1, w, L + 1);
	q(h, w + 1, L + 1);
	q(h - 1, w, L + 1);
	q(h, w - 1, L + 1);

	//리셋 : 현재 위치에서 더 이상 움직일 곳이 없으므로 현재 위치는 경로에서 지우고 이전 위치로 돌아간다.
	A[h][w] = 0;


}

int main() {
	q(1, 1, 1);
	return 0;

}