본문 바로가기

카테고리 없음

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;

}

반응형