BOJ)5913 준규와 사과

문제: icpc.me/5913

(1,1)에서 (5,5)까지 모든 정점을 한번씩 다 들린 뒤 갈 수 있는 경로의 수를 구하는 문제이다.

dfs를 이용하여 나올 수 있는 모든 경우를 탐색해주면 된다.

주의할점은 한번의 경로의 탐색이 끝난 뒤 visited를 해제해주어 다음 경로 탐색 때 그 정점을 방문할 수 있게 해주어야 한다.

#include <cstdio>
#include <algorithm>
using namespace std;
int a[6][6], visited[6][6], k, x, y, r;
int dx[] = { 0,0,1,-1 };
int dy[] = { 1,-1,0,0 };
bool chk(int x, int y) {
    return 0 < x&&x < 6 && 0 < y&&y < 6;
}
void dfs(int x, int y, int z) {
    if (x==5&&y==5) {
        if (z == 25 - k)
            r++;
        return;
    }
    visited[x][y] = 1;
    for (int i = 0; i < 4; i++) {
        int cx = x + dx[i];
        int cy = y + dy[i];
        if (chk(cx, cy) && !visited[cx][cy] && !a[cx][cy])
            dfs(cx, cy, z + 1);
    }
    visited[x][y] = 0;
}
int main() {
    scanf("%d", &k);
    for (int i = 0; i < k; i++) {
        scanf("%d%d", &x, &y);
        a[x][y] = 1;
    }
    dfs(1, 1, 1);
    printf("%d\n", r);
    return 0;
}