dfs 기본

#include <iostream>

using namespace std;

int n, cnt;

int a[5][5];

void DFS(int y, int x)

{

//마지막 위치에 도달하면 경로 개수 1 증가, 종료 조건

if (y == n - 1 && x == n - 1) {

cnt++;

return;

}

//다시 방문하지 않도록 0으로 임시로 바꿈

a[y][x] = 0;

//위쪽으로 방문

if (y > 0 && a[y - 1][x] == 1) DFS(y - 1, x);

//아래쪽으로 방문

if (y < n - 1 && a[y + 1][x] == 1) DFS(y + 1, x);

//왼쪽으로 방문

if (x > 0 && a[y][x - 1] == 1) DFS(y, x - 1);

//오른쪽으로 방문

if (x < n - 1 && a[y][x + 1] == 1) DFS(y, x + 1);

//1로 다시 복원

a[y][x] = 1;

}

int main() {

cin >> n;

int i, j;

for (i = 0; i < n; i++) {

for (j = 0; j < n; j++) {

cin >> a[i][j];

}

}

DFS(0, 0);

cout << cnt << endl;

return 0;

}